{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decode Ways II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDecodings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解码方法 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一条包含字母&nbsp;<code>A-Z</code> 的消息通过以下的方式进行了 <strong>编码</strong> ：</p>\n",
    "\n",
    "<pre>\n",
    "'A' -&gt; \"1\"\n",
    "'B' -&gt; \"2\"\n",
    "...\n",
    "'Z' -&gt; \"26\"</pre>\n",
    "\n",
    "<p>要 <strong>解码</strong> 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，<code>\"11106\"</code> 可以映射为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>\"AAJF\"</code> 对应分组 <code>(1 1 10 6)</code></li>\n",
    "\t<li><code>\"KJF\"</code> 对应分组 <code>(11 10 6)</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意，像 <code>(1 11 06)</code> 这样的分组是无效的，因为 <code>\"06\"</code> 不可以映射为 <code>'F'</code> ，因为 <code>\"6\"</code> 与 <code>\"06\"</code> 不同。</p>\n",
    "\n",
    "<p><strong>除了</strong> 上面描述的数字字母映射方案，编码消息中可能包含 <code>'*'</code> 字符，可以表示从 <code>'1'</code> 到 <code>'9'</code> 的任一数字（不包括 <code>'0'</code>）。例如，编码字符串 <code>\"1*\"</code> 可以表示 <code>\"11\"</code>、<code>\"12\"</code>、<code>\"13\"</code>、<code>\"14\"</code>、<code>\"15\"</code>、<code>\"16\"</code>、<code>\"17\"</code>、<code>\"18\"</code> 或 <code>\"19\"</code> 中的任意一条消息。对 <code>\"1*\"</code> 进行解码，相当于解码该字符串可以表示的任何编码消息。</p>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，由数字和 <code>'*'</code> 字符组成，返回 <strong>解码</strong> 该字符串的方法 <strong>数目</strong> 。</p>\n",
    "\n",
    "<p>由于答案数目可能非常大，返回&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;的&nbsp;<b>模</b>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"*\"\n",
    "<strong>输出：</strong>9\n",
    "<strong>解释：</strong>这一条编码消息可以表示 \"1\"、\"2\"、\"3\"、\"4\"、\"5\"、\"6\"、\"7\"、\"8\" 或 \"9\" 中的任意一条。\n",
    "可以分别解码成字符串 \"A\"、\"B\"、\"C\"、\"D\"、\"E\"、\"F\"、\"G\"、\"H\" 和 \"I\" 。\n",
    "因此，\"*\" 总共有 9 种解码方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"1*\"\n",
    "<strong>输出：</strong>18\n",
    "<strong>解释：</strong>这一条编码消息可以表示 \"11\"、\"12\"、\"13\"、\"14\"、\"15\"、\"16\"、\"17\"、\"18\" 或 \"19\" 中的任意一条。\n",
    "每种消息都可以由 2 种方法解码（例如，\"11\" 可以解码成 \"AA\" 或 \"K\"）。\n",
    "因此，\"1*\" 共有 9 * 2 = 18 种解码方法。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"2*\"\n",
    "<strong>输出：</strong>15\n",
    "<strong>解释：</strong>这一条编码消息可以表示 \"21\"、\"22\"、\"23\"、\"24\"、\"25\"、\"26\"、\"27\"、\"28\" 或 \"29\" 中的任意一条。\n",
    "\"21\"、\"22\"、\"23\"、\"24\"、\"25\" 和 \"26\" 由 2 种解码方法，但 \"27\"、\"28\" 和 \"29\" 仅有 1 种解码方法。\n",
    "因此，\"2*\" 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s[i]</code> 是 <code>0 - 9</code> 中的一位数字或字符 <code>'*'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decode-ways-ii](https://leetcode.cn/problems/decode-ways-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decode-ways-ii](https://leetcode.cn/problems/decode-ways-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"*\"', '\"1*\"', '\"2*\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        def check1(c):\n",
    "            if c == \"*\":\n",
    "                return 9\n",
    "            if c == '0':\n",
    "                return 0\n",
    "            return 1\n",
    "        \n",
    "        def check2(c1,c2):\n",
    "            if c1 == c2 == '*':\n",
    "                return 15\n",
    "            if c2 == '*':\n",
    "                if c1 == '1':\n",
    "                    return 9\n",
    "                if c1 == '2':\n",
    "                    return 6\n",
    "                return 0\n",
    "            if c1 == '*':\n",
    "                if c2 <= '6':\n",
    "                    return 2\n",
    "                return 1\n",
    "            if c1 != '0' and int(c1)*10 + int(c2) <= 26:\n",
    "                return 1\n",
    "            return 0\n",
    "        a,b,c = 0,1,0\n",
    "        for i in range(len(s)):\n",
    "            c = b * check1(s[i])\n",
    "            if i > 0:\n",
    "                c += a * check2(s[i-1],s[i])\n",
    "            c %= (10**9+7)\n",
    "            a,b = b,c\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#解码方法2，\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        #dp[:i]表示0到i上的解码方案数目，dp[i]=c1*dp[i-1]+c2*dp[i-2]\n",
    "        def decode1(c):\n",
    "            if c=='0':return 0\n",
    "            if c=='*':return 9\n",
    "            return 1\n",
    "        def decode2(c1,c2):\n",
    "            if c1=='*'and c2=='*':return 15 #11-19,21-26共15种选择\n",
    "            if c1=='*':\n",
    "                return 2 if c2<='6' else 1\n",
    "            if c2=='*':\n",
    "                if c1=='1':return 9\n",
    "                if c1=='2':return 6\n",
    "                return 0\n",
    "            num=int(c1)*10+int(c2)\n",
    "            if num>=10 and num<=26:return 1\n",
    "            else:return 0\n",
    "        mod=10**9+7\n",
    "        n=len(s)\n",
    "        dp=[0]*(n+1)\n",
    "        dp[0]=1\n",
    "        for i in range(1,n+1):\n",
    "            dp[i]=decode1(s[i-1])*dp[i-1]+((decode2(s[i-2],s[i-1])if i>=2 else 0)*dp[i-2])\n",
    "            dp[i]=dp[i]%mod\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        modnum = 10**9+7\n",
    "        lens = len(s)\n",
    "        # @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            now = s[l:r+1]\n",
    "            if len(now) == 0:\n",
    "                return 1\n",
    "            if len(now) == 1:\n",
    "                if now == '*':\n",
    "                    return 9\n",
    "                elif now == '0':\n",
    "                    return 0\n",
    "                else:\n",
    "                    return 1\n",
    "            res = 0\n",
    "            if now[-2] == '*':\n",
    "                if now[-1] == '*':\n",
    "                    res = 15\n",
    "                elif int(now[-1]) <= 6:\n",
    "                    res = 2\n",
    "                else:\n",
    "                    res = 1\n",
    "            elif int(now[-2]) == 1:\n",
    "                if now[-1] == '*':\n",
    "                    res = 9\n",
    "                else:\n",
    "                    res = 1\n",
    "            elif int(now[-2]) == 2:\n",
    "                if now[-1] == '*':\n",
    "                    res = 6\n",
    "                elif int(now[-1]) <= 6:\n",
    "                    res = 1\n",
    "                else:\n",
    "                    res = 0\n",
    "            return (res*dfs(l, r-2) + dfs(l, r-1)*dfs(r,r))%modnum\n",
    "        # return dfs(0, lens-1)\n",
    "        dp = [0 for _ in range(lens+1)]\n",
    "        dp[0] = 1\n",
    "        for i in range(lens):\n",
    "            res1 = res2 = 0\n",
    "            if s[i] == '*':\n",
    "                res1 = 9\n",
    "            elif s[i] == '0':\n",
    "                res1 = 0\n",
    "            else:\n",
    "                res1 = 1\n",
    "            dp[i+1] = (dp[i+1] + res1*dp[i]) % modnum\n",
    "            if i > 0:\n",
    "                # 情况1**\n",
    "                if s[i-1] == '*':\n",
    "                    if s[i] == '*':\n",
    "                        res2 = 15\n",
    "                    elif int(s[i]) <= 6:\n",
    "                        res2 = 2\n",
    "                    else:\n",
    "                        res2 = 1\n",
    "                # 情况 1*\n",
    "                elif s[i-1] == '1':\n",
    "                    if s[i] == '*':\n",
    "                        res2 = 9\n",
    "                    else:\n",
    "                        res2 = 1\n",
    "                elif s[i-1] == '2':\n",
    "                    if s[i] == '*':\n",
    "                        res2 = 6\n",
    "                    elif int(s[i]) <= 6:\n",
    "                        res2 = 1\n",
    "                dp[i+1] = (dp[i+1] + res2*dp[i-1]) % modnum\n",
    "        return dp[lens]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        MOD=10**9+7\n",
    "        n=len(s)\n",
    "        dp1=[0]*n\n",
    "        dp2=[0]*n\n",
    "        dp1[0]=9 if s[0]=='*' else 0 if s[0]=='0' else 1\n",
    "        def get_base_for_dp1(ch):\n",
    "            if ch=='0':\n",
    "                return 0\n",
    "            if ch=='*':\n",
    "                return 9\n",
    "            return 1\n",
    "        def get_base_for_dp2(lch,ch):\n",
    "            if lch=='*':\n",
    "                if ch=='*':\n",
    "                    return 15\n",
    "                elif int(ch) <=6:\n",
    "                    return 2\n",
    "                else:\n",
    "                    return 1\n",
    "            lch=int(lch)\n",
    "            if lch <1 or lch>2:\n",
    "                return 0\n",
    "            if lch==2:\n",
    "                return 6 if ch=='*' else 0 if ch in '789' else 1\n",
    "            if lch==1:\n",
    "                return 9 if ch=='*' else 1\n",
    "        for i in range(1,n):\n",
    "            lch,ch=s[i-1],s[i]\n",
    "            b1=get_base_for_dp1(ch)\n",
    "            b2=get_base_for_dp2(lch,ch)\n",
    "            dp1[i]=((dp2[i-1]+dp1[i-1])*b1)%MOD\n",
    "            if lch!='*':\n",
    "                dp2[i]=(dp1[i-1]*b2)%MOD\n",
    "            else:\n",
    "                dp2[i]=(b2 * (1 if i==1 else (dp1[i-2]+dp2[i-2])))%MOD\n",
    "        return (dp1[-1]+dp2[-1])%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        MOD=10**9+7\n",
    "        n=len(s)\n",
    "        dp1=[0]*n\n",
    "        dp2=[0]*n\n",
    "        dp1[0]=9 if s[0]=='*' else 0 if s[0]=='0' else 1\n",
    "        def get_base_for_dp1(ch):\n",
    "            if ch=='0':\n",
    "                return 0\n",
    "            if ch=='*':\n",
    "                return 9\n",
    "            return 1\n",
    "        def get_base_for_dp2(lch,ch):\n",
    "            if lch in '03456789':\n",
    "                return 0\n",
    "            if lch =='2':\n",
    "                return 6 if ch=='*' else 0 if ch in '789' else 1\n",
    "            if lch == '1':\n",
    "                return 9 if ch=='*' else 1\n",
    "            if lch=='*':\n",
    "                if ch=='*':\n",
    "                    return 15\n",
    "                elif ch in '0123456':\n",
    "                    return 2\n",
    "                else:\n",
    "                    return 1\n",
    "        for i in range(1,n):\n",
    "            lch,ch=s[i-1],s[i]\n",
    "            b1=get_base_for_dp1(ch)\n",
    "            b2=get_base_for_dp2(lch,ch)\n",
    "            dp1[i]=((dp2[i-1]+dp1[i-1])*b1)%MOD\n",
    "            if lch!='*':\n",
    "                dp2[i]=(dp1[i-1]*b2)%MOD\n",
    "            else:\n",
    "                dp2[i]=(b2 * (1 if i==1 else (dp1[i-2]+dp2[i-2])))%MOD\n",
    "        print(dp1)\n",
    "        print(dp2)\n",
    "        return (dp1[-1]+dp2[-1])%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        # dp[i]代表下标从0到i时的[i位被孤立方法数，i位与上一位相连的方法数]\n",
    "        length = len(s)\n",
    "        dp = [[0] * 2 for _ in range(length)]\n",
    "        # 初始化对于i=0是，与上一位相连的方法数都是0；被孤立的方法数：如果是0就无法解码了;1-9是1,*是9\n",
    "        if s[0] == '0':\n",
    "            return 0\n",
    "        elif s[0] == '*':\n",
    "            dp[0] = [9, 0]\n",
    "        else:\n",
    "            dp[0] = [1, 0]\n",
    "\n",
    "        # 写状态转移方程：\n",
    "        cur = 1  # cur是现在的指针位置\n",
    "        while cur <= length - 1:\n",
    "            if s[cur] == '*':  # 如果cur的位置上是*\n",
    "                if s[cur - 1] == '*':  # 如果cur-1的位置上是*\n",
    "                    if cur-2<0:\n",
    "                        dp[cur]=[81,15]\n",
    "                    else:\n",
    "                        dp[cur] = [sum(dp[cur - 1]) * 9, sum(dp[cur - 2])*15]\n",
    "                elif int(s[cur - 1]) != 1 and int(s[cur - 1]) != 2:\n",
    "                    dp[cur] = [sum(dp[cur - 1]) * 9, 0]\n",
    "                elif int(s[cur - 1]) == 1:\n",
    "                    dp[cur] = [sum(dp[cur - 1]) * 9, dp[cur - 1][0] * 9]\n",
    "                else:\n",
    "                    dp[cur] = [sum(dp[cur - 1]) * 9, dp[cur - 1][0] * 6]\n",
    "\n",
    "            elif int(s[cur]) == 0:  # 如果cur的位置上是0：\n",
    "                if s[cur - 1] == '*':  # 如果cur-1的位置上是*\n",
    "                    if cur-2<0:\n",
    "                        dp[cur]=[0,2]\n",
    "                    else:\n",
    "                        dp[cur] = [0, sum(dp[cur - 2]) * 2]\n",
    "                elif int(s[cur - 1]) != 1 and int(s[cur - 1]) != 2:  # cur-1位置上是3-9\n",
    "                    return 0\n",
    "                else:  # cur-1的位置上是1/2\n",
    "                    dp[cur] = [0, dp[cur - 1][0]]\n",
    "            else:  # cur的位置上是数字并且不为0\n",
    "                if s[cur - 1] == '*':\n",
    "                    if int(s[cur]) < 7:\n",
    "                        if cur-2<0:\n",
    "                            dp[cur]=[9,2]\n",
    "                        else:\n",
    "                            dp[cur] = [sum(dp[cur - 1]), sum(dp[cur - 2]) * 2]\n",
    "                    else:\n",
    "                        if cur-2<0:\n",
    "                            dp[cur]=[9,0]\n",
    "                        else:\n",
    "                            dp[cur] = [sum(dp[cur - 1]), sum(dp[cur - 2]) ]\n",
    "                elif int(s[cur - 1]) == 1:  # 如果说之前一位为1\n",
    "                    dp[cur] = [sum(dp[cur - 1]), dp[cur - 1][0]]\n",
    "                elif int(s[cur - 1]) == 2 and int(s[cur]) < 7:\n",
    "                    dp[cur] = [sum(dp[cur - 1]), dp[cur - 1][0]]\n",
    "                else:\n",
    "                    # 其他都是没办法cur位上的数字没办法和cur-1位置上连起来的方法数\n",
    "                    dp[cur] = [sum(dp[cur - 1]), 0]\n",
    "            dp[cur][0]=(int)(dp[cur][0]% (10 ** 9 + 7))\n",
    "            dp[cur][1]=(int)(dp[cur][1]% (10 ** 9 + 7))\n",
    "            cur += 1\n",
    "        return sum(dp[length - 1]) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "\n",
    "        # top to bottom\n",
    "        # cache={}\n",
    "\n",
    "        # length =len(s)\n",
    "\n",
    "        # def dp_help(n):\n",
    "        #     if n>=length :\n",
    "        #         return 1\n",
    "        #     if n in cache:\n",
    "        #         return cache[n]\n",
    "            \n",
    "        #     if s[n]==\"0\":\n",
    "        #         cache[n]=0\n",
    "        #         return cache[n]\n",
    "        #     elif n+1<length:\n",
    "        #         if s[n]!=\"*\" and int(s[n])<2:\n",
    "        #             if  s[n+1]!=\"*\" :\n",
    "        #                 cache[n]= (dp_help(n+1)+dp_help(n+2))%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]= (dp_help(n+1)+ dp_help(n+2)*9)%(10**9+7)\n",
    "        #         elif s[n]!=\"*\" and int(s[n])==2:\n",
    "        #             if s[n+1]!=\"*\" and int(s[n+1])<=6:\n",
    "        #                 cache[n]=(dp_help(n+1)+dp_help(n+2))%(10**9+7)\n",
    "        #             elif s[n+1]==\"*\":\n",
    "        #                 cache[n]= (dp_help(n+1)+dp_help(n+2)*6)%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]= dp_help(n+1)%(10**9+7)\n",
    "        #         elif s[n]==\"*\" and s[n+1]!=\"*\" :\n",
    "        #             if  int(s[n+1])<=6:\n",
    "        #                 cache[n]= (9* dp_help(n+1)  + 2*dp_help(n+2))%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]= (9* dp_help(n+1) + dp_help(n+2))%(10**9+7)\n",
    "                \n",
    "        #         elif s[n]==\"*\" and s[n+1]==\"*\" :\n",
    "        #             # can't contain numbers that start \"0\" and \"10\",\"20\", totally 11\n",
    "        #             cache[n]= (9* dp_help(n+1) + 15* dp_help(n+2))%(10**9+7)\n",
    "        #         else:\n",
    "        #             cache[n] =dp_help(n+1)%(10**9+7)\n",
    "                    \n",
    "        #         cache[n] = cache[n] %(10**9+7)\n",
    "        #         return cache[n]\n",
    "                \n",
    "        #     else:\n",
    "        #         if s[n]!=\"*\":\n",
    "        #             cache[n] = 1\n",
    "        #             return cache[n]\n",
    "        #         else:\n",
    "        #             cache[n] = 9\n",
    "        #             return cache[n]\n",
    "\n",
    "        # return dp_help(0)%(10**9+7)\n",
    "\n",
    "\n",
    "        # bottom to top\n",
    "        cache ={i:0 for i in range(len(s)+1)}\n",
    "        cache[len(s)]=1\n",
    "        # cache[-2]=\n",
    "        length=len(s)\n",
    "        for n in range(len(s)-1,-1,-1):\n",
    "            if s[n]==\"0\":\n",
    "                cache[n]=0\n",
    "            elif n+1<length:\n",
    "                if s[n]!=\"*\" and int(s[n])<2:\n",
    "                    if  s[n+1]!=\"*\" :\n",
    "                        cache[n]= (cache[n+1]+cache[n+2])%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]= (cache[n+1]+ cache[n+2]*9)%(10**9+7)\n",
    "                elif s[n]!=\"*\" and int(s[n])==2:\n",
    "                    if s[n+1]!=\"*\" and int(s[n+1])<=6:\n",
    "                        cache[n]= (cache[n+1]+cache[n+2])%(10**9+7)\n",
    "                    elif s[n+1]==\"*\":\n",
    "                        cache[n]= (cache[n+1]+cache[n+2]*6)%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]=cache[n+1]%(10**9+7)\n",
    "    \n",
    "                elif s[n]==\"*\" and s[n+1]!=\"*\" :\n",
    "                    if  int(s[n+1])<=6:\n",
    "                        cache[n]= (9* cache[n+1]  + 2*cache[n+2])%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]= (9* cache[n+1] + cache[n+2])%(10**9+7)\n",
    "                \n",
    "                elif s[n]==\"*\" and s[n+1]==\"*\" :\n",
    "                    # can't contain numbers that start \"0\" and \"10\",\"20\", totally 11\n",
    "                    cache[n]= (9* cache[n+1] + 15* cache[n+2])%(10**9+7)\n",
    "                else:\n",
    "                    cache[n] =cache[n+1]%(10**9+7)\n",
    "                    \n",
    "                # cache[n] = cache[n]%(10**9+7)\n",
    "            else:\n",
    "                if s[n]!=\"*\":\n",
    "                    cache[n] = 1\n",
    "                \n",
    "                    \n",
    "                else:\n",
    "                    cache[n] = 9\n",
    "        print(cache)   \n",
    "        return cache[0]%(10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        \n",
    "        table = [[0, 0] for i in range(len(s))]\n",
    "        if s[0] == '*':\n",
    "            table[0][0] = 9\n",
    "            table[0][1] = 0\n",
    "        elif s[0] == '0':\n",
    "            table[0][0] = 0\n",
    "            table[0][1] = 0\n",
    "        else:\n",
    "            table[0][0] = 1\n",
    "            table[0][1] = 0\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] == '*':\n",
    "                if s[i-1] == '0':\n",
    "                    table[i][0] = (sum(table[i-1]) * 9) % (1e9 + 7)\n",
    "                    table[i][1] = 0\n",
    "                elif s[i-1] == '1':\n",
    "                    table[i][0] = (sum(table[i-1]) * 9) % (1e9 + 7)\n",
    "                    table[i][1] = (table[i-1][0] * 9) % (1e9 + 7)\n",
    "                elif s[i-1] == '2':\n",
    "                    table[i][0] = (sum(table[i-1]) * 9) % (1e9 + 7)\n",
    "                    table[i][1] = (table[i-1][0] * 6) % (1e9 + 7)\n",
    "                elif s[i-1] == '*':\n",
    "                    table[i][0] = (sum(table[i-1]) * 9) % (1e9 + 7)\n",
    "                    table[i][1] = 15 if i < 2 else (sum(table[i-2]) * 15) % (1e9+7)\n",
    "                else:\n",
    "                    table[i][0] = (sum(table[i-1]) * 9) % (1e9 + 7)\n",
    "                    table[i][1] = 0\n",
    "            elif s[i] == '0':\n",
    "                table[i][0] = 0\n",
    "                if s[i-1] in ['1', '2']:\n",
    "                    table[i][1] = table[i-1][0]\n",
    "                elif s[i-1] == '*':\n",
    "                    table[i][1] = 2 if i < 2 else (sum(table[i-2]) * 2) % (1e9+7)\n",
    "                else:\n",
    "                    table[i][1] = 0\n",
    "            else:\n",
    "                table[i][0] = sum(table[i-1]) % (1e9 + 7)\n",
    "                if s[i-1] == '0':\n",
    "                    table[i][1] = 0\n",
    "                elif s[i-1] == '*':\n",
    "                    if s[i] <= '6':\n",
    "                        table[i][1] = 2 if i < 2 else (sum(table[i-2]) * 2) % (1e9+7)\n",
    "                    else:\n",
    "                        table[i][1] = 1 if i < 2 else sum(table[i-2])\n",
    "                else:\n",
    "                    table[i][1] = table[i-1][0] if int(s[i-1:i+1]) <= 26 else 0\n",
    "        print(table)\n",
    "        return int(sum(table[-1]) % (1e9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        d,d1 = {-1:1},{-1:0}\n",
    "        mod = 1000000007\n",
    "        ln = None\n",
    "        for i in range(len(s)):\n",
    "            c = s[i]\n",
    "            if i==0:\n",
    "                if c==\"*\":\n",
    "                    d[i]=9\n",
    "                    ln = 11\n",
    "                else:\n",
    "                    n = int(c)\n",
    "                    if n==0:\n",
    "                        return 0\n",
    "                    d[i]=1\n",
    "                    ln = n\n",
    "                d1[i]=0\n",
    "            else:\n",
    "                if c==\"*\":\n",
    "                    d[i]=(d[i-1]+d1[i-1])*9\n",
    "                    if ln==11:\n",
    "                        d1[i]=(d1[i-2]+d[i-2])*15\n",
    "                    elif ln==1:\n",
    "                        d1[i]=(d1[i-2]+d[i-2])*9\n",
    "                    elif ln==2:\n",
    "                        d1[i]=(d1[i-2]+d[i-2])*6\n",
    "                    else:\n",
    "                        d1[i]=0\n",
    "                    ln=11\n",
    "                    d[i]%=mod\n",
    "                    d1[i]%=mod\n",
    "                else:\n",
    "                    n = int(c)\n",
    "                    if n==0:\n",
    "                        d[i]=0\n",
    "                        if ln==1 or ln==2:\n",
    "                            d1[i]=(d1[i-2]+d[i-2])\n",
    "                        elif ln==11:\n",
    "                            d1[i]=(d1[i-2]+d[i-2])*2\n",
    "                        else:\n",
    "                            d1[i]=0\n",
    "                    else:\n",
    "                        d[i]=d[i-1]+d1[i-1]\n",
    "                        if ln==1:\n",
    "                            d1[i]=(d1[i-2]+d[i-2])\n",
    "                        elif ln==2:\n",
    "                            if n<7:\n",
    "                                d1[i]=d1[i-2]+d[i-2]\n",
    "                            else:\n",
    "                                d1[i]=0\n",
    "                        elif ln==11:\n",
    "                            if n<7:\n",
    "                                d1[i]=(d1[i-2]+d[i-2])*2\n",
    "                            else:\n",
    "                                d1[i]=(d1[i-2]+d[i-2])\n",
    "                        else:\n",
    "                            d1[i]=0\n",
    "                    ln = n\n",
    "                    d[i]%=mod\n",
    "                    d1[i]%=mod\n",
    "        return (d[len(s)-1]+d1[len(s)-1])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        if s=='' or s[0]=='0': return 0\n",
    "        const=10**9+7\n",
    "        temp=[[0,0,0,0,0] for i in s] #[0-6/,7-9/,/1,/2,/3-9] 其中/在前表示前面有分割，/在后表示前面没分割\n",
    "        if s[0]=='*': \n",
    "            temp[0][2]=1\n",
    "            temp[0][3]=1\n",
    "            temp[0][4]=7\n",
    "        elif s[0]=='1': temp[0][2]=1\n",
    "        elif s[0]=='2': temp[0][3]=1\n",
    "        elif s[0] in '3456789': temp[0][4]=1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]=='*': \n",
    "                temp[i][0]=(temp[i-1][2]+temp[i-1][3])*6\n",
    "                temp[i][1]=(temp[i-1][2])*3\n",
    "                temp[i][2]=sum(temp[i-1])\n",
    "                temp[i][3]=sum(temp[i-1])\n",
    "                temp[i][4]=(sum(temp[i-1]))*7\n",
    "            elif s[i]=='1': \n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][2]=sum(temp[i-1])\n",
    "            elif s[i]=='2':\n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][3]=sum(temp[i-1])\n",
    "            elif s[i] in '3456': \n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][4]=sum(temp[i-1])\n",
    "            elif s[i] in '789':\n",
    "                temp[i][1]=temp[i-1][2]\n",
    "                temp[i][4]=sum(temp[i-1])\n",
    "            else: #s[i]='0'\n",
    "                if s[i-1] in'03456789': return 0\n",
    "                elif s[i-1]=='1': temp[i][0]=temp[i-1][2]\n",
    "                elif s[i-1]=='2': temp[i][0]=temp[i-1][3]\n",
    "                elif s[i-1]=='*': temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "            for j in range(5): temp[i][j]=temp[i][j]%const\n",
    "        #print(temp)\n",
    "        return sum(temp[-1]) % const\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        #动态规划\n",
    "        #dp[i][last] 前i个字符，最后一位解码last = 1,2,3,..26\n",
    "        dp = [[0 for _ in range(27)] for _ in range(len(s))]\n",
    "        if s[0] == '*':\n",
    "            for i in range(1,10):\n",
    "                dp[0][i] = 1\n",
    "        else:\n",
    "            dp[0][int(s[0])] = 1\n",
    "        cnt = 0\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i] == '*':\n",
    "                cur = list(range(1,10))\n",
    "            else:\n",
    "                cur = [int(s[i])]\n",
    "            cnt = 0\n",
    "            for last in range(1,27): \n",
    "                cnt = (cnt + dp[i-1][last]) % (10**9+7)\n",
    "            for c in cur:\n",
    "                dp[i][c] = cnt\n",
    "                dp[i][10+c] = dp[i-1][1]                   \n",
    "                if 20+c < 27:\n",
    "                    dp[i][20+c] = dp[i-1][2]\n",
    "        cnt = 0\n",
    "        for c in range(1,27):\n",
    "            cnt = (cnt + dp[-1][c]) % (10**9+7)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        if s=='' or s[0]=='0': return 0\n",
    "        const=10**9+7\n",
    "        temp=[[0,0,0,0,0] for i in s] #[0-6/,7-9/,/1,/2,/3-9] 其中/在前表示前面有分割，/在后表示前面没分割\n",
    "        if s[0]=='*': \n",
    "            temp[0][2]=1\n",
    "            temp[0][3]=1\n",
    "            temp[0][4]=7\n",
    "        elif s[0]=='1': temp[0][2]=1\n",
    "        elif s[0]=='2': temp[0][3]=1\n",
    "        elif s[0] in '3456789': temp[0][4]=1\n",
    "        for i in range(1,len(s)):\n",
    "            if s[i]=='*': \n",
    "                temp[i][0]=(temp[i-1][2]+temp[i-1][3])*6\n",
    "                temp[i][1]=(temp[i-1][2])*3\n",
    "                temp[i][2]=sum(temp[i-1])\n",
    "                temp[i][3]=sum(temp[i-1])\n",
    "                temp[i][4]=(sum(temp[i-1]))*7\n",
    "            elif s[i]=='1': \n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][2]=sum(temp[i-1])\n",
    "            elif s[i]=='2':\n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][3]=sum(temp[i-1])\n",
    "            elif s[i] in '3456': \n",
    "                temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "                temp[i][4]=sum(temp[i-1])\n",
    "            elif s[i] in '789':\n",
    "                temp[i][1]=temp[i-1][2]\n",
    "                temp[i][4]=sum(temp[i-1])\n",
    "            else: #s[i]='0'\n",
    "                if s[i-1] in'03456789': return 0\n",
    "                elif s[i-1]=='1': temp[i][0]=temp[i-1][2]\n",
    "                elif s[i-1]=='2': temp[i][0]=temp[i-1][3]\n",
    "                elif s[i-1]=='*': temp[i][0]=temp[i-1][2]+temp[i-1][3]\n",
    "            for j in range(5): temp[i][j]=temp[i][j]%const\n",
    "        print(temp)\n",
    "        return sum(temp[-1]) % const\n",
    "\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 28 ms ... 99 % ... 14.9 MB ... 27 %\n",
    "        #  time: O(n)\n",
    "        # space: O(n) ... 可优化至 O(1)\n",
    "        \n",
    "        n, mod = len(s), 10**9 + 7\n",
    "        dp = [0]*(n+1)    # dp[i] 表示 s[:i] 的解码方法总数\n",
    "        dp[0] = 1\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch == '*':\n",
    "                dp[i+1] = dp[i] * 9                                                              #  * 解析为 1-9\n",
    "                if i:\n",
    "                    if   s[i-1] == '1': dp[i+1] += dp[i-1] * 9                                   # 1* 解析为 11-19\n",
    "                    elif s[i-1] == '2': dp[i+1] += dp[i-1] * 6                                   # 2* 解析为 21-26\n",
    "                    elif s[i-1] == '*': dp[i+1] += dp[i-1] * 15                                  # ** 解析为 11-19 及 21-26\n",
    "            elif ch == '0':\n",
    "                if i:\n",
    "                    if   s[i-1] in '12': dp[i+1] = dp[i-1]                                       # 10/20 解析为 10/20\n",
    "                    elif s[i-1] == '*':  dp[i+1] = dp[i-1] * 2                                   #    *0 解析为 10 及 20\n",
    "            else:\n",
    "                dp[i+1] = dp[i]                                                                  #  1- 9 解析为  1- 9\n",
    "                if i:\n",
    "                    if   s[i-1] == '1': dp[i+1] += dp[i-1]                                       # 11-19 解析为 11-19\n",
    "                    elif s[i-1] == '2': dp[i+1] += dp[i-1] if ch in '123456' else 0              # 21-29 解析为 21-26\n",
    "                    elif s[i-1] == '*': dp[i+1] += dp[i-1] * 2 if ch in '123456' else dp[i-1]    # *1-*9 解析为【11-16 及 21-26】或【17-19】\n",
    "            dp[i+1] %= mod\n",
    "        return dp[-1]\n",
    "\n",
    "'''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        mod=pow(10,9)+7\n",
    "        n=len(s)\n",
    "\n",
    "        #dp[i][j]表示当前字符为'j'且与前面不相连的方法数目，1<=j<=9\n",
    "        #dp[i][0]表示当前字符为'0'的数目（必与前面连接而不与后面相连）\n",
    "        #dp[i][10]表示当前字符与前面相连\n",
    "\n",
    "        dp=[[0]*11 for i in range(n)]\n",
    "        if(s[0]=='0'):\n",
    "            return 0\n",
    "        elif(s[0]=='*'):\n",
    "            for i in range(1,10):\n",
    "                dp[0][i]=1\n",
    "        else:\n",
    "            dp[0][ord(s[0])-ord('0')]=1\n",
    "\n",
    "        for i in range(1,n):\n",
    "            if(s[i]=='*'):\n",
    "                if(s[i-1]!='0'):\n",
    "                    #令当前字符与前面字符相连\n",
    "                    dp[i][10]+=(9*dp[i-1][1]+6*dp[i-1][2])%mod\n",
    "                    #不相连\n",
    "                    for k in range(1,10):\n",
    "                        dp[i][k]=sum(dp[i-1])%mod\n",
    "                else:#前字符为'0'\n",
    "                    for k in range(1,10):\n",
    "                        dp[i][k]=dp[i-1][0]\n",
    "\n",
    "           #当前字符为'0'\n",
    "            elif(s[i]=='0'):\n",
    "                dp[i][0]=sum(dp[i-1][1:3])%mod\n",
    "            #s[i]~[1,9]\n",
    "            else:\n",
    "                #与前相连\n",
    "                if(s[i]>='1' and s[i]<='6'):\n",
    "                    dp[i][10]+=(dp[i-1][1]+dp[i-1][2])%mod\n",
    "                else:\n",
    "                    dp[i][10]+=dp[i-1][1]%mod\n",
    "                #与前不相连\n",
    "                dp[i][ord(s[i])-ord('0')]+=sum(dp[i-1])%mod\n",
    "        return sum(dp[-1])%mod\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        dp = [[0 for _ in range(11)] for _ in range(n+1)]\n",
    "        dp[0][10] = 1\n",
    "        for i in range(n):\n",
    "            if s[i] == '*':\n",
    "                for j in range(9):\n",
    "                    dp[i+1][j] = (dp[i+1][j]+dp[i][10])%mod\n",
    "                dp[i+1][10] = (dp[i+1][10]+dp[i][10]*9)%mod\n",
    "                dp[i+1][10] = (dp[i+1][10]+dp[i][1]*9)%mod\n",
    "                dp[i+1][10] = (dp[i+1][10]+dp[i][2]*6)%mod\n",
    "            else:\n",
    "                num = int(s[i]) \n",
    "                if num != 0:\n",
    "                    dp[i+1][10] = (dp[i+1][10]+dp[i][10])%mod\n",
    "                dp[i+1][num] = (dp[i+1][num]+dp[i][10])%mod\n",
    "                dp[i+1][10] = (dp[i+1][10]+dp[i][1])%mod\n",
    "                if num <= 6:\n",
    "                    dp[i+1][10] = (dp[i+1][10]+dp[i][2])%mod\n",
    "        \n",
    "        # print(dp)\n",
    "        return dp[n][10]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        if s[0]=='0':return 0\n",
    "        n=len(s)\n",
    "        mod=int(1e9+7)\n",
    "        dp=[[0]*27 for _ in range(n+1)]\n",
    "        if s[0]=='*':\n",
    "            for i in range(1,10):\n",
    "                dp[1][i]=1\n",
    "        else :\n",
    "            dp[1][int(s[0])]=1\n",
    "\n",
    "        for i in range(2,n+1):\n",
    "            if s[i-1]=='*':\n",
    "                now=sum(dp[i-1])\n",
    "                for j in range(1,10):\n",
    "                    dp[i][j]=now%mod\n",
    "                for j in range(11,20):\n",
    "                    dp[i][j]=dp[i-1][1]\n",
    "                for j in range(21,27):\n",
    "                    dp[i][j]=dp[i-1][2]\n",
    "            elif int(s[i-1])==0:\n",
    "                dp[i][10]=dp[i-1][1]\n",
    "                dp[i][20]=dp[i-1][2]\n",
    "            elif int(s[i-1])<=6:\n",
    "                dp[i][int(s[i-1])]=sum(dp[i-1])\n",
    "                dp[i][int(s[i-1])]=dp[i][int(s[i-1])]%mod\n",
    "                dp[i][10+int(s[i-1])]=dp[i-1][1]\n",
    "                dp[i][20+int(s[i-1])]=dp[i-1][2]\n",
    "            else:\n",
    "                dp[i][int(s[i-1])]=sum(dp[i-1])\n",
    "                dp[i][int(s[i-1])]=dp[i][int(s[i-1])]%mod\n",
    "                dp[i][10+int(s[i-1])]=dp[i-1][1]\n",
    "        return sum(dp[n])%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "@cache\n",
    "def func1(s):\n",
    "    if not s:\n",
    "        return 1\n",
    "\n",
    "    if s[0] == '0':\n",
    "        return 0\n",
    "\n",
    "    n = len(s)\n",
    "    if n == 1:\n",
    "        if s == '*':\n",
    "            return 9\n",
    "        return 1 if s != '0' else 0\n",
    "\n",
    "    if n == 2:\n",
    "        a, b = s\n",
    "        if a == '0':\n",
    "            return 0\n",
    "        if a == '1':\n",
    "            if b == '*':\n",
    "                return 18  # 9+9\n",
    "            return 2 if b != '0' else 1\n",
    "        if a == '2':\n",
    "            if b == '*':\n",
    "                return 15  # 6 + 9\n",
    "            return 2 if b in '123456' else 1\n",
    "        if a == '*':\n",
    "            if b == '0':\n",
    "                return 2\n",
    "            if b in '123456':\n",
    "                return 11  # 2+9\n",
    "            if b in '789':\n",
    "                return 10  # 1+9\n",
    "            return 96  # 9+6+81\n",
    "        # a = 3456789\n",
    "        if b == '*':\n",
    "            return 9\n",
    "        return 1 if b != '0' else 0\n",
    "\n",
    "    pos = n // 2\n",
    "\n",
    "    a, b, c = s[pos - 1], s[pos], s[pos + 1]\n",
    "    if b == '*':\n",
    "        v = 0\n",
    "        for i in range(1, 10):\n",
    "            b = str(i)\n",
    "            v += res_mid(s, pos, b) + res_left(s, pos, a, b) + res_right(s, pos, b, c)\n",
    "    else:\n",
    "        v = res_mid(s, pos, b) + res_left(s, pos, a, b) + res_right(s, pos, b, c)\n",
    "    return v\n",
    "\n",
    "\n",
    "def res_mid(s, pos, b):\n",
    "    if b == '0':\n",
    "        return 0\n",
    "    vright = func1(s[pos + 1:])\n",
    "    if vright == 0:\n",
    "        return 0\n",
    "    return vright * func1(s[:pos])\n",
    "\n",
    "\n",
    "def res_left(s, pos, a, b):\n",
    "    if a == '1' or (a == '2' and b in '0123456'):\n",
    "        return func1(s[:pos - 1]) * func1(s[pos + 1:])\n",
    "    if a == '*':\n",
    "        return res_left(s, pos, '1', b) + res_left(s, pos, '2', b)\n",
    "    return 0\n",
    "\n",
    "\n",
    "def res_right(s, pos, b, c):\n",
    "    if c == '*':\n",
    "        if b == '1':\n",
    "            return func1(s[:pos]) * func1(s[pos + 2:]) * 9\n",
    "        if b == '2':\n",
    "            return func1(s[:pos]) * func1(s[pos + 2:]) * 6\n",
    "\n",
    "    if b == '1' or (b == '2' and c in '0123456'):\n",
    "        return func1(s[:pos]) * func1(s[pos + 2:])\n",
    "    return 0\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        return func1(s) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "from datetime import datetime\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        def timer_func(func):\n",
    "            def wrap_func(*args, **kwargs):\n",
    "                t = datetime.utcnow()\n",
    "                current_time = t.strftime(\"%H:%M:%S.%f\")\n",
    "                indent = ' '*args[1]\n",
    "                print(f'{indent} Function {func.__name__!r} with loc {args[1]} was called on {current_time}')\n",
    "                result = func(*args, **kwargs)\n",
    "                t = datetime.utcnow()\n",
    "                current_time = t.strftime(\"%H:%M:%S.%f\")\n",
    "                print(f'{indent} Function {func.__name__!r} with loc {args[1]} finished on {current_time}')\n",
    "                return result\n",
    "            return wrap_func\n",
    "        n = len(s)\n",
    "        \n",
    "        #@timer_func\n",
    "        @lru_cache\n",
    "        def helper(s: str, loc: int, n: int) -> int:\n",
    "            if loc == n:\n",
    "                return 1\n",
    "            if loc == n-1:\n",
    "                if s[loc] == '*':\n",
    "                    return 9\n",
    "                elif s[loc] == '0':\n",
    "                    return 0\n",
    "                return 1\n",
    "            else:\n",
    "                if s[loc] == '*':\n",
    "                    if s[loc+1] == '0':\n",
    "                        return 2*helper(s,loc+2,n) % int(1e9+7)\n",
    "                    elif s[loc+1] == '*':\n",
    "                        return (15*helper(s,loc+2,n) + 9*helper(s,loc+1,n)) % int(1e9+7)\n",
    "                    elif '7' <= s[loc+1] <= '9':\n",
    "                        return  (helper(s,loc+2,n) + 9*helper(s,loc+1,n)) % int(1e9+7)\n",
    "                    else:\n",
    "                        return (2*helper(s,loc+2,n) + 9*helper(s,loc+1,n)) % int(1e9+7)\n",
    "                elif s[loc] == '0':\n",
    "                    return 0\n",
    "                elif s[loc] == '1':\n",
    "                    if s[loc+1] == '*':\n",
    "                        return (helper(s,loc+1,n) + 9 * helper(s,loc+2,n)) % int(1e9+7)\n",
    "                    return (helper(s,loc+1,n) + helper(s,loc+2,n)) % int(1e9+7)\n",
    "                elif s[loc] == '2':\n",
    "                    if s[loc+1] == '*':\n",
    "                        return (helper(s,loc+1,n) + 6 * helper(s,loc+2,n)) % int(1e9+7)\n",
    "                    elif '0 ' < s[loc+1] < '7':\n",
    "                        return  (helper(s,loc+1,n) + helper(s,loc+2,n)) % int(1e9+7)\n",
    "                    else:\n",
    "                        return helper(s,loc+2,n)\n",
    "                else:\n",
    "                    return helper(s, loc+1, n)\n",
    "            \n",
    "        return helper(s,0,n)\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        \n",
    "        n = len(s)\n",
    "        \n",
    "\n",
    "        @lru_cache\n",
    "        def helper(s: str, loc: int, n: int) -> int:\n",
    "            if loc == n:\n",
    "                return 1\n",
    "            if loc == n-1:\n",
    "                if s[loc] == '*':\n",
    "                    return 9\n",
    "                elif s[loc] == '0':\n",
    "                    return 0\n",
    "                return 1\n",
    "            else:\n",
    "                if s[loc] == '*':\n",
    "                    if s[loc+1] == '0':\n",
    "                        return 2*helper(s,loc+2,n)\n",
    "                    elif s[loc+1] == '*':\n",
    "                        return 15*helper(s,loc+2,n) + 9*helper(s,loc+1,n)\n",
    "                    elif '7' <= s[loc+1] <= '9':\n",
    "                        return  helper(s,loc+2,n) + 9*helper(s,loc+1,n)\n",
    "                    else:\n",
    "                        return 2*helper(s,loc+2,n) + 9*helper(s,loc+1,n)\n",
    "                elif s[loc] == '0':\n",
    "                    return 0\n",
    "                elif s[loc] == '1':\n",
    "                    if s[loc+1] == '*':\n",
    "                        return helper(s,loc+1,n) + 9 * helper(s,loc+2,n)\n",
    "                    return helper(s,loc+1,n) + helper(s,loc+2,n)\n",
    "                elif s[loc] == '2':\n",
    "                    if s[loc+1] == '*':\n",
    "                        return helper(s,loc+1,n) + 6 * helper(s,loc+2,n)\n",
    "                    elif '0 ' < s[loc+1] < '7':\n",
    "                        return  helper(s,loc+1,n) + helper(s,loc+2,n)\n",
    "                    else:\n",
    "                        return helper(s,loc+2,n)\n",
    "                else:\n",
    "                    return helper(s, loc+1, n)\n",
    "            \n",
    "        return helper(s,0,n) % int(1e9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        upperbound = {\n",
    "            1:9,\n",
    "            2:6,\n",
    "            3:0,4:0,5:0,6:0,7:0,8:0,9:0\n",
    "        }\n",
    "        cache = {}\n",
    "        def dp(i):\n",
    "            # print(i, s[i:i+3])\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "            if i >= n:\n",
    "                return 1 \n",
    "            if s[i] == \"0\":\n",
    "                return 0 \n",
    "\n",
    "            if i == n-2: ## 两位数\n",
    "                c1, c2 = s[i], s[i+1]\n",
    "                if c1 == \"*\":\n",
    "                    if c2 == \"*\": #\" **\"\n",
    "                        return 18+15+9*7\n",
    "                    else:         # \"*d\"\n",
    "                        d2 = int(c2)\n",
    "                        if d2 == 0:\n",
    "                            return 2\n",
    "                        elif d2 <= 6:\n",
    "                            return 9+2\n",
    "                        else:\n",
    "                            return 9\n",
    "                else:\n",
    "                    d1 = int(c1)\n",
    "                    if c2 == \"*\":  # \"d*\"\n",
    "                        if d1 == 1:\n",
    "                            return 18\n",
    "                        elif d1 == 2:\n",
    "                            return 15\n",
    "                        else:\n",
    "                            return 9\n",
    "                # \"dd\"\n",
    "                d1, d2 = int(c1), int(c2)\n",
    "                if d2 == 0:\n",
    "                    return 1 if d1 <= 2 else 0     # \"d10\"\n",
    "                else:\n",
    "                    if d2 <= upperbound[d1]:\n",
    "                        return 2 # \"d1d2\", \"d1|d2\"\n",
    "                    else:\n",
    "                        return 1 # \"d1|d2\"\n",
    "\n",
    "            elif i == n-1: ## 一位数\n",
    "                if s[i] == \"*\":\n",
    "                    return 9\n",
    "                return 1\n",
    "\n",
    "            # else:\n",
    "            c1, c2, c3 = s[i], s[i+1], s[i+2]\n",
    "            if c1 == \"*\":   # \"*__\"\n",
    "                # print(\"  >\", c1, c2, c3)\n",
    "                if c2 == \"*\": # \"**_\"\n",
    "                    if c3 == \"*\": # \"***\"\n",
    "                        # c = 9*9*dp(i+2) + (18+15+1*7)*dp(i+2) + 9*dp(i+1) # \"*|*|*\" + \"**|*\" + \"*|**\"\n",
    "                        if i < n-3:\n",
    "                            c4 = s[i+3]\n",
    "                            if c4 == \"0\":\n",
    "                                c = 9*9*dp(i+2) + (9+6)*dp(i+2) # \"*|*|*\" + \"**|*\"\n",
    "                            else:\n",
    "                                c = (9+6)*dp(i+2) + 9*dp(i+1) # \"*|*|*\" + \"**|*\" + \"*|**\"\n",
    "                        else:\n",
    "                            c = 9*9*9+15*9+9*15\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:         # \"**d\"\n",
    "                        c = (9+6)*dp(i+2) + 9*dp(i+1) # \"**|d\" + \"*|*d\"\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                else:       # \"*d_\"\n",
    "                    d2 = int(c2) \n",
    "                    if d2 == 0:       # \"*0|_\"\n",
    "                        c = 2*dp(i+2)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "                    elif d2 <= 6:     # \"*6|_\" + \"*|d_\"\n",
    "                        c = 2*dp(i+2)+9*dp(i+1)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:             # \"*7|_\" + \"*|d_\"\n",
    "                        c = 1*dp(i+2)+9*dp(i+1)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "            # \"d*_\"\n",
    "            if c2 == \"*\":\n",
    "                # print(\" >>\", c1, c2, c3)\n",
    "                d1 = int(c1)\n",
    "                if d1 == 0:\n",
    "                    return 0\n",
    "                c = dp(i+1) # (d|*_)\n",
    "                if c3 != \"0\":\n",
    "                    if d1 == 1: # (d*|_)\n",
    "                        c += 9*dp(i+2)\n",
    "                    elif d1 == 2:\n",
    "                        c += 6*dp(i+2)\n",
    "                    else:\n",
    "                        c += 0#*dp(i+1)\n",
    "                cache[i] = c % (1e9+7)\n",
    "                return cache[i]\n",
    "            # \"dd_\"\n",
    "            if c3 == \"*\": # \"dd*\"\n",
    "                # print(\">>>\", c1, c2, c3)\n",
    "                d1, d2 = int(c1), int(c2)\n",
    "                if d2 == 0:\n",
    "                    c = dp(i+2) if d1 <= 2 else 0\n",
    "                    cache[i] = c % (10e9+7)\n",
    "                    return cache[i]\n",
    "                elif d2 <= upperbound[d1]:\n",
    "                    c = dp(i+1)+dp(i+2)\n",
    "                    cache[i] = c % (10e9+7)\n",
    "                    return cache[i]\n",
    "                else:\n",
    "                    c = dp(i+2) # \"d|d|*\"\n",
    "                    if d2 == 1: # \"d|d*|...\"\n",
    "                        c += 9*dp(i+3)\n",
    "                    elif d2 == 2:\n",
    "                        c += 6*dp(i+3) \n",
    "                    else:\n",
    "                        c += 0#*dp(i+3)\n",
    "                    cache[i] = c% (1e9+7)\n",
    "                    return cache[i]\n",
    "\n",
    "            # \"ddd\"\n",
    "            print(\"  *\", c1, c2, c3)\n",
    "            d1, d2, d3 = int(c1), int(c2), int(c3)\n",
    "            # d1 不可能为 0\n",
    "            if d3 == 0:\n",
    "                c = 1*(dp(i+1)) #\"d|d0\"\n",
    "                cache[i] = c % (1e9+7)\n",
    "                return cache[i]\n",
    "            else:\n",
    "                # 不用管 d3 了\n",
    "                if d2 == 0:\n",
    "                    c = 1*(dp(i+2)) if d1 <= 2 else 0\n",
    "                    cache[i] = c \n",
    "                    return cache[i]\n",
    "                else:\n",
    "                    if d2 <= upperbound[d1]:\n",
    "                        c = dp(i+1) + dp(i+2)\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:\n",
    "                        c = dp(i+1)\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "        c = dp(0) % (1e9+7)\n",
    "\n",
    "        # print(cache)\n",
    "        return int(c)\n",
    "    \"\"\"\n",
    "    620, 33.78%;\n",
    "    104.9, 5.40%.\n",
    "    \"\"\"\n",
    "                 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        dp = [0] * (len(s) + 1)\n",
    "        if s[-1] == \"*\":\n",
    "            dp[-2] = 9\n",
    "        elif s[-1] != \"0\":\n",
    "            dp[-2] = 1\n",
    "        dp[-1] = 1\n",
    "        for i in range(len(s) - 2, -1, -1):\n",
    "            if s[i] == \"*\":\n",
    "                dp[i] = 9 * dp[i + 1]\n",
    "                if s[i + 1] == \"*\":\n",
    "                    dp[i] += 15 * dp[i + 2]\n",
    "                elif s[i + 1] <= \"6\":\n",
    "                    dp[i] += 2 * dp[i + 2]\n",
    "                else:\n",
    "                    dp[i] += dp[i + 2]\n",
    "            elif s[i] == \"0\":\n",
    "                continue\n",
    "            else:\n",
    "                dp[i] = dp[i + 1]\n",
    "                if s[i] == \"1\":\n",
    "                    if s[i + 1] == \"*\":\n",
    "                        dp[i] += 9 * dp[i + 2]\n",
    "                    else:\n",
    "                        dp[i] += dp[i + 2]\n",
    "                elif s[i] == \"2\":\n",
    "                    if s[i + 1] == \"*\":\n",
    "                        dp[i] += 6 * dp[i + 2]\n",
    "                    elif s[i + 1] <= \"6\":\n",
    "                        dp[i] += dp[i + 2]\n",
    "        return dp[0] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        upperbound = {\n",
    "            1:9,\n",
    "            2:6,\n",
    "            3:0,4:0,5:0,6:0,7:0,8:0,9:0\n",
    "        }\n",
    "        cache = {}\n",
    "        def dp(i):\n",
    "            # print(i, s[i:i+3])\n",
    "            if i in cache:\n",
    "                return cache[i]\n",
    "            if i >= n:\n",
    "                return 1 \n",
    "            if s[i] == \"0\":\n",
    "                return 0 \n",
    "\n",
    "            if i == n-2: ## 两位数\n",
    "                c1, c2 = s[i], s[i+1]\n",
    "                if c1 == \"*\":\n",
    "                    if c2 == \"*\": #\" **\"\n",
    "                        return 18+15+9*7\n",
    "                    else:         # \"*d\"\n",
    "                        d2 = int(c2)\n",
    "                        if d2 == 0:\n",
    "                            return 2\n",
    "                        elif d2 <= 6:\n",
    "                            return 9+2\n",
    "                        else:\n",
    "                            return 9\n",
    "                else:\n",
    "                    d1 = int(c1)\n",
    "                    if c2 == \"*\":  # \"d*\"\n",
    "                        if d1 == 1:\n",
    "                            return 18\n",
    "                        elif d1 == 2:\n",
    "                            return 15\n",
    "                        else:\n",
    "                            return 9\n",
    "                # \"dd\"\n",
    "                d1, d2 = int(c1), int(c2)\n",
    "                if d2 == 0:\n",
    "                    return 1 if d1 <= 2 else 0     # \"d10\"\n",
    "                else:\n",
    "                    if d2 <= upperbound[d1]:\n",
    "                        return 2 # \"d1d2\", \"d1|d2\"\n",
    "                    else:\n",
    "                        return 1 # \"d1|d2\"\n",
    "\n",
    "            elif i == n-1: ## 一位数\n",
    "                if s[i] == \"*\":\n",
    "                    return 9\n",
    "                return 1\n",
    "\n",
    "            # else:\n",
    "            c1, c2, c3 = s[i], s[i+1], s[i+2]\n",
    "            if c1 == \"*\":   # \"*__\"\n",
    "                print(\"  >\", c1, c2, c3)\n",
    "                if c2 == \"*\": # \"**_\"\n",
    "                    if c3 == \"*\": # \"***\"\n",
    "                        # c = 9*9*dp(i+2) + (18+15+1*7)*dp(i+2) + 9*dp(i+1) # \"*|*|*\" + \"**|*\" + \"*|**\"\n",
    "                        if i < n-3:\n",
    "                            c4 = s[i+3]\n",
    "                            if c4 == \"0\":\n",
    "                                c = 9*9*dp(i+2) + (9+6)*dp(i+2) # \"*|*|*\" + \"**|*\"\n",
    "                            else:\n",
    "                                c = (9+6)*dp(i+2) + 9*dp(i+1) # \"*|*|*\" + \"**|*\" + \"*|**\"\n",
    "                        else:\n",
    "                            c = 9*9*9+15*9+9*15\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:         # \"**d\"\n",
    "                        c = (9+6)*dp(i+2) + 9*dp(i+1) # \"**|d\" + \"*|*d\"\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                else:       # \"*d_\"\n",
    "                    d2 = int(c2) \n",
    "                    if d2 == 0:       # \"*0|_\"\n",
    "                        c = 2*dp(i+2)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "                    elif d2 <= 6:     # \"*6|_\" + \"*|d_\"\n",
    "                        c = 2*dp(i+2)+9*dp(i+1)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:             # \"*7|_\" + \"*|d_\"\n",
    "                        c = 1*dp(i+2)+9*dp(i+1)\n",
    "                        cache[i] = c% (1e9+7)\n",
    "                        return cache[i]\n",
    "            # \"d*_\"\n",
    "            if c2 == \"*\":\n",
    "                print(\" >>\", c1, c2, c3)\n",
    "                d1 = int(c1)\n",
    "                if d1 == 0:\n",
    "                    return 0\n",
    "                c = dp(i+1) # (d|*_)\n",
    "                if c3 != \"0\":\n",
    "                    if d1 == 1: # (d*|_)\n",
    "                        c += 9*dp(i+2)\n",
    "                    elif d1 == 2:\n",
    "                        c += 6*dp(i+2)\n",
    "                    else:\n",
    "                        c += 0#*dp(i+1)\n",
    "                cache[i] = c % (1e9+7)\n",
    "                return cache[i]\n",
    "            # \"dd_\"\n",
    "            if c3 == \"*\": # \"dd*\"\n",
    "                print(\">>>\", c1, c2, c3)\n",
    "                d1, d2 = int(c1), int(c2)\n",
    "                if d2 == 0:\n",
    "                    c = dp(i+2) if d1 <= 2 else 0\n",
    "                    cache[i] = c % (10e9+7)\n",
    "                    return cache[i]\n",
    "                elif d2 <= upperbound[d1]:\n",
    "                    c = dp(i+1)+dp(i+2)\n",
    "                    cache[i] = c % (10e9+7)\n",
    "                    return cache[i]\n",
    "                else:\n",
    "                    c = dp(i+2) # \"d|d|*\"\n",
    "                    if d2 == 1: # \"d|d*|...\"\n",
    "                        c += 9*dp(i+3)\n",
    "                    elif d2 == 2:\n",
    "                        c += 6*dp(i+3) \n",
    "                    else:\n",
    "                        c += 0#*dp(i+3)\n",
    "                    cache[i] = c% (1e9+7)\n",
    "                    return cache[i]\n",
    "\n",
    "            # \"ddd\"\n",
    "            print(\"  *\", c1, c2, c3)\n",
    "            d1, d2, d3 = int(c1), int(c2), int(c3)\n",
    "            # d1 不可能为 0\n",
    "            if d3 == 0:\n",
    "                c = 1*(dp(i+1)) #\"d|d0\"\n",
    "                cache[i] = c % (1e9+7)\n",
    "                return cache[i]\n",
    "            else:\n",
    "                # 不用管 d3 了\n",
    "                if d2 == 0:\n",
    "                    c = 1*(dp(i+2)) if d1 <= 2 else 0\n",
    "                    cache[i] = c \n",
    "                    return cache[i]\n",
    "                else:\n",
    "                    if d2 <= upperbound[d1]:\n",
    "                        c = dp(i+1) + dp(i+2)\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "                    else:\n",
    "                        c = dp(i+1)\n",
    "                        cache[i] = c % (1e9+7)\n",
    "                        return cache[i]\n",
    "        c = dp(0) % (1e9+7)\n",
    "\n",
    "        # print(cache)\n",
    "        return int(c)\n",
    "                 \n",
    "\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def search(self, index, current):\n",
    "        if index == len(self.s):\n",
    "            if current == 0:\n",
    "                return 1\n",
    "            return 0\n",
    "        if self.cache[current][index] != -1:\n",
    "            return self.cache[current][index]\n",
    "        if not current:\n",
    "            # Not *\n",
    "            if self.s[index] != '*':\n",
    "                nextChar = int(self.s[index])\n",
    "                if nextChar == 0:\n",
    "                    ans = 0\n",
    "                else:\n",
    "                    ans = self.search(index + 1, 0)\n",
    "                    if nextChar <= 2:\n",
    "                        ans += self.search(index + 1, nextChar)\n",
    "            # Is *\n",
    "            else:\n",
    "                ans = (9 * self.search(index + 1, 0) +\n",
    "                       self.search(index + 1, 1) + self.search(index + 1, 2))\n",
    "        else:\n",
    "            # Not *\n",
    "            if self.s[index] != '*':\n",
    "                nextChar = int(self.s[index])\n",
    "                current * 10 + nextChar\n",
    "                if current * 10 + nextChar > 26:\n",
    "                    ans = 0\n",
    "                else:\n",
    "                    ans = self.search(index + 1, 0)\n",
    "            # Is *\n",
    "            else:\n",
    "                if current == 1:\n",
    "                    ans = 9 * self.search(index + 1, 0)\n",
    "                else:\n",
    "                    ans = 6 * self.search(index + 1, 0)\n",
    "        ans = ans % 1000000007\n",
    "        self.cache[current][index] = ans\n",
    "        return ans\n",
    "\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        self.cache = []\n",
    "        for _ in range(3):\n",
    "            self.cache.append([-1] * len(s))\n",
    "        self.s = s\n",
    "        return self.search(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [ [0]*27 for _ in range(n+1 ) ] \n",
    "        MOD  = 10**9 + 7\n",
    "        for i,ch in enumerate(s): \n",
    "            if ch=='*':\n",
    "                cs = list(range(1,10))\n",
    "            else:\n",
    "                cs = [ ord(ch) - ord('0') ]\n",
    "            \n",
    "            sum_1 = sum(dp[i-1]) \n",
    "            for c in cs: \n",
    "                if c == 0:\n",
    "                    dp[i][10] += dp[i-1][1] \n",
    "                    dp[i][20] += dp[i-1][2]\n",
    "                elif c <= 6:\n",
    "                    dp[i][c] += sum_1 if i!=0 else 1\n",
    "                    dp[i][10+c] += dp[i-1][1]\n",
    "                    dp[i][20+c] += dp[i-1][2] \n",
    "                elif c <= 9:\n",
    "                    dp[i][c] += sum_1 if i!=0 else 1\n",
    "                    dp[i][10+c] += dp[i-1][1]\n",
    "            \n",
    "            for j in range(1,27):\n",
    "                dp[i][j] %= MOD\n",
    "\n",
    "        return sum( dp[-2] )%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        return self.search(s, 0, {})\n",
    "\n",
    "    def search(self, s, i, table):\n",
    "        if i not in table:\n",
    "            n = len(s)\n",
    "            if i == n:\n",
    "                table[i] = 1\n",
    "            elif i > n:\n",
    "                table[i] = 0\n",
    "            else:\n",
    "                res = 0\n",
    "                if s[i] != '*':\n",
    "                    if s[i] == '0':\n",
    "                        res = 0\n",
    "                    elif s[i] == '1':\n",
    "                        res = self.search(s, i + 1, table)\n",
    "                        if i + 1 < n:\n",
    "                            if s[i + 1] == '*':\n",
    "                                res += self.search(s, i + 2, table) * 9\n",
    "                            else:\n",
    "                                res += self.search(s, i + 2, table)\n",
    "                    elif s[i] == '2':\n",
    "                        if i + 1 == n:\n",
    "                            res = 1\n",
    "                        else:\n",
    "                            if s[i + 1] == '*':\n",
    "                                res = self.search(s, i + 1, table) + self.search(s, i + 2, table) * 6\n",
    "                            elif s[i + 1] == '0':\n",
    "                                res = self.search(s, i + 2, table)\n",
    "                            elif s[i + 1] <= '6':\n",
    "                                res = self.search(s, i + 1, table) + self.search(s, i + 2, table)\n",
    "                            else:\n",
    "                                res = self.search(s, i + 1, table)\n",
    "                    else:\n",
    "                        res = self.search(s, i + 1, table)\n",
    "                else:\n",
    "                    # 3 - 9\n",
    "                    res += self.search(s, i + 1, table) * 7\n",
    "                    # 1\n",
    "                    res += self.search(s, i + 1, table)\n",
    "                    if i + 1 < n:\n",
    "                        if s[i + 1] == '*':\n",
    "                            res += self.search(s, i + 2, table) * 9\n",
    "                        else:\n",
    "                            res += self.search(s, i + 2, table)\n",
    "                    # 2\n",
    "                    if i + 1 == n:\n",
    "                        res += 1\n",
    "                    else:\n",
    "                        if s[i + 1] == '*':\n",
    "                            res += self.search(s, i + 1, table) + self.search(s, i + 2, table) * 6\n",
    "                        elif s[i + 1] == '0':\n",
    "                            res += self.search(s, i + 2, table)\n",
    "                        elif s[i + 1] <= '6':\n",
    "                            res += self.search(s, i + 1, table) + self.search(s, i + 2, table)\n",
    "                        else:\n",
    "                            res += self.search(s, i + 1, table)\n",
    "                table[i] = res % int(1e9 + 7)\n",
    "        return table[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        dp = [-1 for i in range(len(s)+1)]\n",
    "        mod = int(1e9 + 7)\n",
    "        def Decodings(s, i, dp):\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "            if dp[i] != -1:\n",
    "                return dp[i]\n",
    "            ans = Decodings(s, i+1, dp) * (9 if s[i] == '*' else 1)\n",
    "            if i+1 < len(s):\n",
    "                if s[i] != '*':\n",
    "                    if s[i+1] != '*':\n",
    "                        if int(s[i])*10+int(s[i+1]) <= 26:\n",
    "                            ans += Decodings(s, i+2, dp)\n",
    "                    else:\n",
    "                        if s[i] == '1':\n",
    "                            ans += 9 * Decodings(s, i+2, dp)\n",
    "                        if s[i] == '2':\n",
    "                            ans+= 6 * Decodings(s, i+2, dp)\n",
    "                else:\n",
    "                    if s[i+1] != '*':\n",
    "                        if int(s[i+1]) > 6:\n",
    "                            ans += Decodings(s, i+2, dp)\n",
    "                        else:\n",
    "                            ans += 2 * Decodings(s, i+2, dp)\n",
    "                    else:\n",
    "                        ans += 15 * Decodings(s, i+2, dp)\n",
    "            ans %= mod\n",
    "            dp[i] = ans\n",
    "            return ans\n",
    "        \n",
    "        return Decodings(s, 0, dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dp(n):\n",
    "            nonlocal p\n",
    "            if n < 0:\n",
    "                return 1\n",
    "            res = 0\n",
    "            if n - 1 >= 0:\n",
    "                if s[n - 1] == '1':\n",
    "                    if s[n] == '*':\n",
    "                        res += 9 * dp(n - 2)\n",
    "                    else:\n",
    "                        res += dp(n - 2)\n",
    "                elif s[n - 1] == '2':\n",
    "                    if s[n] == '*':\n",
    "                        res += 6 * dp(n - 2)\n",
    "                    elif s[n] <= '6':\n",
    "                        res += dp(n - 2)\n",
    "                elif s[n - 1] == '*':\n",
    "                    if s[n] == '*':\n",
    "                        res += 15 * dp(n - 2)\n",
    "                    elif s[n] <= '6':\n",
    "                        res += 2 * dp(n - 2)\n",
    "                    else:\n",
    "                        res += dp(n - 2)\n",
    "            if s[n] == '*':\n",
    "                res += 9 * dp(n - 1)\n",
    "            elif s[n] != '0':\n",
    "                res += dp(n - 1)\n",
    "            return res % p\n",
    "        p = 10 ** 9 + 7\n",
    "        return dp(len(s) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.d1 = {}\n",
    "        self.d21 = {}\n",
    "        self.d22 = {}\n",
    "\n",
    "    def func1(self,s,start):\n",
    "        '''上一位没有利用这一位'''\n",
    "        if start>=len(s):\n",
    "            return 0\n",
    "        if start==len(s)-1:\n",
    "            if s[start]=='*':\n",
    "                return 9\n",
    "            elif s[start]=='0':\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        \n",
    "        rr = self.d1.get(start)\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "\n",
    "        if s[start]=='0':\n",
    "            return 0\n",
    "        ret = 0\n",
    "        if s[start]=='*':\n",
    "            # * as 1\n",
    "            ret += (self.func1(s,start+1) + self.func2(s,start+1,1))\n",
    "            # * as 2\n",
    "            ret += (self.func1(s,start+1) + self.func2(s,start+1,2))\n",
    "            # * as 3-9\n",
    "            ret += 7*self.func1(s,start+1)\n",
    "        elif s[start]=='1':\n",
    "            ret = (self.func1(s,start+1) + self.func2(s,start+1,1))\n",
    "        elif s[start]=='2':\n",
    "            ret = (self.func1(s,start+1) + self.func2(s,start+1,2))\n",
    "        else:\n",
    "            ret = self.func1(s,start+1)\n",
    "        ret %= 1000000007\n",
    "        self.d1[start] = ret\n",
    "        return ret\n",
    "\n",
    "    def func2(self,s,start,prev):\n",
    "        '''上一位利用了这一位'''\n",
    "        if start>=len(s):\n",
    "            return 0\n",
    "        if start==len(s)-1:\n",
    "            if prev==1:\n",
    "                if s[start]=='*':\n",
    "                    return 9\n",
    "                else:\n",
    "                    return 1\n",
    "            else: # prev = 2\n",
    "                if s[start]=='*':\n",
    "                    return 6\n",
    "                elif s[start] in '0123456':\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "        rr = None\n",
    "        if prev==1:\n",
    "            rr = self.d21.get(start)\n",
    "        else:\n",
    "            rr = self.d22.get(start)\n",
    "        if rr!=None:\n",
    "            return rr\n",
    "\n",
    "        ret = 0\n",
    "        if prev==1:\n",
    "            if s[start]=='*':\n",
    "                # * as 1-9\n",
    "                ret += 9*self.func1(s,start+1)\n",
    "            else:\n",
    "                ret = self.func1(s,start+1)\n",
    "        else: # prev = 2\n",
    "            if s[start]=='*':\n",
    "                # * as 1-6\n",
    "                ret += 6*self.func1(s,start+1)\n",
    "            elif s[start] in '0123456':\n",
    "                ret = self.func1(s,start+1)\n",
    "        ret %= 1000000007\n",
    "        if prev==1:\n",
    "            self.d21[start]=ret\n",
    "        else:\n",
    "            self.d22[start]=ret\n",
    "        return ret\n",
    "\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        return self.func1(s,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "s1 = set(['*0', '*1', '*2', '*3', '*4', '*5', '*6'])\n",
    "s2 = set(['*7', '*8', '*9'])\n",
    "s3 = set(['3*', '4*', '5*', '6*', '7*', '8*', '9*'])\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        f = [inf] * n\n",
    "        # @cache\n",
    "        def dfs(i): \n",
    "            if i == n: return 1\n",
    "            if f[i] != inf: return f[i]\n",
    "            res = 0\n",
    "            if s[i] != '0':\n",
    "                # 解码一个位置\n",
    "                if s[i] == '*':\n",
    "                    res += dfs(i + 1) * 9\n",
    "                else:\n",
    "                    res += dfs(i + 1)\n",
    "                # 解码连续两个位置\n",
    "                # ** 15种\n",
    "                # 1* *可取1-9 9种\n",
    "                # 2* *可取1-6 6种\n",
    "                # 3*-9*  0种\n",
    "                # *0-*6  *可取1,2  2种\n",
    "                # *7-*9  *可取1    1种\n",
    "                if i + 1 < n:\n",
    "                    tmp = s[i:i+2]\n",
    "                    if tmp in s3: \n",
    "                        f[i] = res % MOD\n",
    "                        return f[i]  # 3*-9*  0种\n",
    "                    if tmp == '**': res += dfs(i + 2) * 15\n",
    "                    elif tmp == '1*': res += dfs(i + 2) * 9\n",
    "                    elif tmp == '2*': res += dfs(i + 2) * 6\n",
    "                    elif tmp in s1 : res += dfs(i + 2) * 2\n",
    "                    elif tmp in s2 or 10 <= int(tmp) <= 26: res += dfs(i + 2)\n",
    "            f[i] = res % MOD\n",
    "            return f[i]\n",
    "\n",
    "        return dfs(0) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        self.mod = 10**9+7\n",
    "        self.dp = [-1]*len(s)\n",
    "        def f1(s,i):\n",
    "            if i==len(s):\n",
    "                return 1\n",
    "            if self.dp[i]!=-1:\n",
    "                return self.dp[i]\n",
    "            if s[i]==\"0\":\n",
    "                return 0\n",
    "            ans = f1(s,i+1)*9 if s[i]==\"*\" else f1(s,i+1)*1\n",
    "            if (i+1<len(s)):\n",
    "                if s[i]!=\"*\":\n",
    "                    if s[i+1]!=\"*\":\n",
    "                        if (ord(s[i])-ord(\"0\"))*10+(ord(s[i+1])-ord(\"0\"))<=26:\n",
    "                            ans += f1(s,i+2)\n",
    "                    else:\n",
    "                        if s[i]==\"1\":\n",
    "                            ans += f1(s,i+2)*9\n",
    "                        if s[i]==\"2\":\n",
    "                            ans+=f1(s,i+2)*6\n",
    "                else:\n",
    "                    if s[i+1]!=\"*\":\n",
    "                        if s[i+1]<=\"6\":\n",
    "                            ans += f1(s,i+2)*2\n",
    "                        else:\n",
    "                            ans += f1(s,i+2)\n",
    "                    else:\n",
    "                        ans+=f1(s,i+2)*15\n",
    "            ans = ans%self.mod\n",
    "            self.dp[i] = ans\n",
    "            return ans\n",
    "\n",
    "\n",
    "\n",
    "        return f1(s,0)%(self.mod)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        mod = 10**9+7\n",
    "        n = len(s)\n",
    "        m = [0]*n\n",
    "        def backtrack(idx):\n",
    "            if idx==n:\n",
    "                return 1\n",
    "            if s[idx]==\"0\":\n",
    "                return 0\n",
    "            if m[idx]:\n",
    "                return m[idx]\n",
    "\n",
    "            res = 0\n",
    "            if idx+1==n:\n",
    "                if s[idx]==\"*\": res = 9\n",
    "                else: res = 1\n",
    "            else:\n",
    "                if s[idx:idx+2]==\"**\":\n",
    "                    res = 9*backtrack(idx+1)+(9+6)*backtrack(idx+2)\n",
    "                elif s[idx]==\"*\":\n",
    "                    res = 9*backtrack(idx+1)\n",
    "                    if s[idx+1]<=\"6\":\n",
    "                        res += 2*backtrack(idx+2)\n",
    "                    elif s[idx+1]<=\"9\":\n",
    "                        res += backtrack(idx+2)\n",
    "\n",
    "                elif s[idx+1]==\"*\":\n",
    "                    if s[idx]==\"1\":\n",
    "                        res = backtrack(idx+1)+9*backtrack(idx+2)\n",
    "                    elif s[idx]==\"2\":\n",
    "                        res = backtrack(idx+1)+6*backtrack(idx+2)\n",
    "                    else:\n",
    "                        res = backtrack(idx+1)\n",
    "                elif int(s[idx:idx+2])<=26:\n",
    "                    res = backtrack(idx+1)+backtrack(idx+2)\n",
    "                else:\n",
    "                    res = backtrack(idx+1)\n",
    "            res %= mod\n",
    "            m[idx] = res\n",
    "            return res\n",
    "\n",
    "        return backtrack(0)\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: ####################记忆化搜索\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        MOD = int(1e9 + 7)\n",
    "        n = len(s)\n",
    "        self.memo = [-1] * n \n",
    "\n",
    "        def decodeOneChar(c):\n",
    "            if c == '0': return 0\n",
    "            if c == '*': return 9\n",
    "            return 1\n",
    "        \n",
    "        def decodeTwoChar(c1, c2):\n",
    "            if c1 == '*' and c2 == '*': return 15 # 11,...,19 21,...26\n",
    "            elif c1 == '*':\n",
    "                if c2 <= '6': return 2 # 1 c2, 2 c2\n",
    "                else: return 1 # c2 = 7, c1只能为1\n",
    "            elif c2 == '*':\n",
    "                if c1 == '1': return 9\n",
    "                elif c1 == '2': return 6\n",
    "                else: return 0\n",
    "            else:\n",
    "                twoSum = (ord(c1) - ord('0')) * 10 + ord(c2) - ord('0')\n",
    "                if twoSum >= 10 and twoSum <= 26: return 1\n",
    "                return 0\n",
    "\n",
    "        def dfs(i):\n",
    "            if i == n: return 1\n",
    "            if i > n: return 0\n",
    "            if self.memo[i] != -1: return self.memo[i]\n",
    "            #########################注意这里是乘法\n",
    "            ans = decodeOneChar(s[i]) * dfs(i + 1); ans %= MOD\n",
    "            if i + 1 < n:\n",
    "                ans += decodeTwoChar(s[i], s[i + 1]) * dfs(i + 2); ans %= MOD\n",
    "            self.memo[i] = ans\n",
    "            return ans\n",
    "        return dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        # 前i个\n",
    "        @cache\n",
    "        def f(i):\n",
    "            if i == 0: return 1\n",
    "            if i == 1:\n",
    "                if s[0] == '0': return 0\n",
    "                if s[0] == '*': return 9\n",
    "                return 1\n",
    "            if s[i - 1] == '0':\n",
    "                if s[i - 2] in ['1', '2']:\n",
    "                    return f(i - 2) % mod\n",
    "                if s[i - 2] == '*':\n",
    "                    return f(i - 2) * 2 % mod\n",
    "                return 0\n",
    "            if s[i - 1] == '*':\n",
    "                if s[i - 2] == '0':\n",
    "                    return f(i - 1) * 9 % mod\n",
    "                if s[i - 2] == '*':\n",
    "                    # 1、前一个*转换成1时，本*转化成[1,9]都能贴上去\n",
    "                    # 2、前一个*转换成2时，本*转化成[1,6]都能贴上去\n",
    "                    # 3、前一个*转化成[3,9]时，本*贴不上去，本*转换成[1,9]。\n",
    "                    # 4、前一个*转换[1,2]时，本*贴不上去，本*转换成[1,9]。\n",
    "                    p1 = f(i - 2) * 9 % mod     # 前一个*转换成1\n",
    "                    p2 = f(i - 2) * 6 % mod # 前一个*转换成2\n",
    "                    p3 = 9 * f(i - 1) % mod  # 前一个*转换成3-9 _ _ 3 *\n",
    "                    return (p1 + p2 + p3) % mod\n",
    "\n",
    "                if s[i - 2] == '1':\n",
    "                    return (f(i - 2) * 9 % mod + f(i - 1) * 9 % mod) % mod\n",
    "                if s[i - 2] == '2':\n",
    "                    return (f(i - 2) * 6 % mod + f(i - 1) * 9 % mod) % mod\n",
    "\n",
    "                return f(i - 1) * 9 % mod\n",
    "\n",
    "            # 当前字符是1-9\n",
    "            if s[i - 2] == '0':\n",
    "                return f(i - 1)\n",
    "            if s[i - 2] == '*':\n",
    "                p1 = f(i - 1)\n",
    "                # _ _ * 7\n",
    "                if s[i - 1] in ['7', '8', '9']:\n",
    "                    # 前一个*转化成1的时候可以贴上去\n",
    "                    return p1 + f(i - 2)\n",
    "                # _ _ * 6\n",
    "                return (2 * f(i - 2) + p1) % mod\n",
    "\n",
    "            if s[i - 2] == '1':\n",
    "                return (f(i - 1) + f(i - 2)) % mod\n",
    "            if s[i - 2] == '2':\n",
    "                if s[i - 1] in ['7', '8', '9']:\n",
    "                    return f(i - 1)\n",
    "                return (f(i - 1) + f(i - 2)) % mod\n",
    "\n",
    "            # _ _ 5 8\n",
    "            # 3 <= s[i - 2] <= 9\n",
    "            return f(i - 1)\n",
    "\n",
    "        return f(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        record = [-1]*len(s)\n",
    "        mode = int(1e9+7)\n",
    "        def get_result(idx):\n",
    "            if idx>=len(s):\n",
    "                return 1\n",
    "            if record[idx]!=-1:\n",
    "                return record[idx]\n",
    "            res = 0\n",
    "            if s[idx]=='0':\n",
    "                record[idx] = res\n",
    "                return res\n",
    "            t = get_result(idx+1)\n",
    "            t1 = 0\n",
    "            if idx+1<len(s):\n",
    "                t1 = get_result(idx+2)\n",
    "            if s[idx]=='*':\n",
    "                res =(res+t*9)%mode\n",
    "                if idx+1<len(s):\n",
    "                    if s[idx+1]=='*':\n",
    "                        res = (res+t1*15)%mode\n",
    "                    else:\n",
    "                        res = (res+t1)%mode\n",
    "                        if '0'<= s[idx+1]<'7':\n",
    "                            res=(res+t1)%mode\n",
    "            else:\n",
    "                res= (res+t)%mode\n",
    "                if idx+1<len(s):\n",
    "                    if s[idx]=='1':\n",
    "                        if s[idx+1]=='*':\n",
    "                            res = (res+t1*9)%mode\n",
    "                        else:\n",
    "                            res = (res+t1)%mode\n",
    "                    if s[idx]=='2':\n",
    "                        if s[idx+1]=='*':\n",
    "                            res = (res+t1*6)%mode\n",
    "                        elif  '0'<= s[idx+1]<'7':\n",
    "                            res=(res+t1)%mode\n",
    "            record[idx] = res\n",
    "            return res\n",
    "\n",
    "        return get_result(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        arr = [None] * len(s)\n",
    "        arr[0] = 1 if s[0] != '*' else 9\n",
    "        if s[0] == '0' :\n",
    "            arr[0] = 0\n",
    "        def rec(i):\n",
    "            if i < 0:\n",
    "                return 1\n",
    "            if arr[i] is None:\n",
    "                arr[i] = 0\n",
    "                if s[i-1] == '*':\n",
    "                    if s[i] == '0':\n",
    "                        arr[i] = 2*rec(i-2)\n",
    "                    elif s[i] == '*':\n",
    "                        arr[i] = 9*rec(i-1) + 15*rec(i-2)\n",
    "                    elif int(s[i]) < 7:\n",
    "                        arr[i] = rec(i-1) + 2*rec(i-2)\n",
    "                    else:\n",
    "                        arr[i] = rec(i-1) + rec(i-2)\n",
    "                elif s[i-1] == '1':\n",
    "                    if s[i] == '0':\n",
    "                        arr[i] = rec(i-2)\n",
    "                    elif s[i] == '*':\n",
    "                        arr[i] = 9*rec(i-1) + 9*rec(i-2)\n",
    "                    else:\n",
    "                        arr[i] = rec(i-1) + rec(i-2)\n",
    "                elif s[i-1] == '2':\n",
    "                    if s[i] == '0':\n",
    "                        arr[i] = rec(i-2)\n",
    "                    elif s[i] == '*':\n",
    "                        arr[i] = 9*rec(i-1) + 6*rec(i-2)\n",
    "                    elif int(s[i]) < 7:\n",
    "                        arr[i] = rec(i-1) + rec(i-2)\n",
    "                    else:\n",
    "                        arr[i] = rec(i-1)\n",
    "                else :\n",
    "                    if s[i] == '0':\n",
    "                        arr[i] = 0\n",
    "                    elif s[i] == '*':\n",
    "                        arr[i] = 9*rec(i-1)\n",
    "                    else:\n",
    "                        arr[i] = rec(i-1)\n",
    "            return arr[i]% (10**9 + 7)\n",
    "        return rec(len(s)-1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        visited = [-1]*len(s)\n",
    "        def one(t):\n",
    "            if t[0]=='*':\n",
    "                return 9\n",
    "            elif t[0]=='0':\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        def two(t):\n",
    "            if t[0]=='*' and t[1]=='*':\n",
    "                return 15\n",
    "            elif t[0]=='*':\n",
    "                return 1 if t[1]>'6' else 2\n",
    "            elif t[0]=='0' or t[0]>'2' or (t[0]>'1' and t[1]>'6'):\n",
    "                return 0\n",
    "            elif t[1]=='*':\n",
    "                return 9 if t[0]=='1' else 6\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        def digui(i):\n",
    "            if i==len(s):\n",
    "                return 1\n",
    "            if i>len(s):\n",
    "                return 0\n",
    "            if visited[i]!=-1:\n",
    "                return visited[i]\n",
    "            if len(s)-i>=2:\n",
    "                res = one(s[i:i+1])*digui(i+1)+two(s[i:i+2])*digui(i+2)\n",
    "            else:\n",
    "                res = one(s[i:i + 1]) * digui(i + 1)\n",
    "            visited[i] = res%1000000007\n",
    "            return res%1000000007\n",
    "\n",
    "        ans = digui(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(10000000)\n",
    "M_N = 10 ** 9 + 7\n",
    "ORD_6 = ord('6')\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "\n",
    "        last_index = len(s) - 1\n",
    "        cache = [None] * len(s)\n",
    "\n",
    "        def rec(idx, prev_num):\n",
    "            if idx > last_index:\n",
    "                return 1\n",
    "\n",
    "            c = s[idx]\n",
    "\n",
    "            if prev_num is not None:\n",
    "                nr = rec(idx + 1, None)\n",
    "                if prev_num == '1':\n",
    "                    if c == '*':\n",
    "                        return 9 * nr\n",
    "                    else:\n",
    "                        return nr\n",
    "                if prev_num == '2':\n",
    "                    if c == '*':\n",
    "                        return 6 * nr\n",
    "                    if ord(c) <= ORD_6:\n",
    "                        return nr\n",
    "                    return 0\n",
    "\n",
    "            if c == '0':\n",
    "                return 0\n",
    "\n",
    "            if idx == last_index:\n",
    "                return 9 if c == '*' else 1\n",
    "\n",
    "            if cache[idx] is not None:\n",
    "                return cache[idx]\n",
    "\n",
    "            r = rec(idx + 1, None)\n",
    "            if c == '1' or c == '2':\n",
    "                r = r + rec(idx + 1, c)\n",
    "            elif c == '*':\n",
    "                if idx < last_index and s[idx+1] == '0':\n",
    "                    r = 2 * rec(idx + 2, None)\n",
    "                else:\n",
    "                    r = 9 * r + rec(idx + 1, '1') + rec(idx + 1, '2')\n",
    "\n",
    "            r = r % M_N\n",
    "            cache[idx] = r\n",
    "            return r\n",
    "\n",
    "        return rec(0, None)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = {}\n",
    "        base = 10**9 + 7\n",
    "\n",
    "        def decode(i):\n",
    "            if i>n:\n",
    "                return 0\n",
    "            if i==n:\n",
    "                return 1\n",
    "            if s[i] == '0':\n",
    "                return 0\n",
    "            if i in dp:\n",
    "                return dp[i]\n",
    "\n",
    "            ans = 0\n",
    "            if s[i] in '3456789':\n",
    "                ans = decode(i+1)\n",
    "            if s[i] in '1*':\n",
    "                ans = decode(i+1)\n",
    "                if i <= n-2:\n",
    "                    if s[i+1] == '*':\n",
    "                        ans += 9*decode(i+2)\n",
    "                    else:\n",
    "                        ans += decode(i+2)\n",
    "            if s[i] in '2*':\n",
    "                ans += decode(i+1)\n",
    "                if i <= n-2:\n",
    "                    if s[i+1] == '*':\n",
    "                        ans += 6*decode(i+2)\n",
    "                    elif s[i+1] in '0123456':\n",
    "                        ans += decode(i+2)\n",
    "            if s[i] == '*':\n",
    "                ans += 7*decode(i+1)\n",
    "            \n",
    "            ans = ans%base\n",
    "            dp[i] = ans\n",
    "            return ans\n",
    "\n",
    "        return decode(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "\n",
    "        # top to bottom\n",
    "        cache={}\n",
    "\n",
    "        length =len(s)\n",
    "\n",
    "        def dp_help(n):\n",
    "            if n>=length :\n",
    "                return 1\n",
    "            if n in cache:\n",
    "                return cache[n]\n",
    "            \n",
    "            if s[n]==\"0\":\n",
    "                cache[n]=0\n",
    "                return cache[n]\n",
    "            elif n+1<length:\n",
    "                if s[n]!=\"*\" and int(s[n])<2:\n",
    "                    if  s[n+1]!=\"*\" :\n",
    "                        cache[n]= (dp_help(n+1)+dp_help(n+2))%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]= (dp_help(n+1)+ dp_help(n+2)*9)%(10**9+7)\n",
    "                elif s[n]!=\"*\" and int(s[n])==2:\n",
    "                    if s[n+1]!=\"*\" and int(s[n+1])<=6:\n",
    "                        cache[n]=(dp_help(n+1)+dp_help(n+2))%(10**9+7)\n",
    "                    elif s[n+1]==\"*\":\n",
    "                        cache[n]= (dp_help(n+1)+dp_help(n+2)*6)%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]= dp_help(n+1)%(10**9+7)\n",
    "                elif s[n]==\"*\" and s[n+1]!=\"*\" :\n",
    "                    if  int(s[n+1])<=6:\n",
    "                        cache[n]= (9* dp_help(n+1)  + 2*dp_help(n+2))%(10**9+7)\n",
    "                    else:\n",
    "                        cache[n]= (9* dp_help(n+1) + dp_help(n+2))%(10**9+7)\n",
    "                \n",
    "                elif s[n]==\"*\" and s[n+1]==\"*\" :\n",
    "                    # can't contain numbers that start \"0\" and \"10\",\"20\", totally 11\n",
    "                    cache[n]= (9* dp_help(n+1) + 15* dp_help(n+2))%(10**9+7)\n",
    "                else:\n",
    "                    cache[n] =dp_help(n+1)%(10**9+7)\n",
    "                    \n",
    "                cache[n] = cache[n] %(10**9+7)\n",
    "                return cache[n]\n",
    "                \n",
    "            else:\n",
    "                if s[n]!=\"*\":\n",
    "                    cache[n] = 1\n",
    "                    return cache[n]\n",
    "                else:\n",
    "                    cache[n] = 9\n",
    "                    return cache[n]\n",
    "\n",
    "        return dp_help(0)%(10**9+7)\n",
    "\n",
    "\n",
    "        # # bottom to top\n",
    "        # cache =[0]* (len(s)+1)\n",
    "        # cache[-1]=1\n",
    "        # # cache[-2]=\n",
    "        # length=len(s)\n",
    "        # for n in range(len(s)-1,-1,-1):\n",
    "        #     if s[n]==\"0\":\n",
    "        #         cache[n]=0\n",
    "        #     elif n+1<length:\n",
    "        #         if s[n]!=\"*\" and int(s[n])<2:\n",
    "        #             if  s[n+1]!=\"*\" :\n",
    "        #                 cache[n]= (cache[n+1]+cache[n+2])%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]= (cache[n+1]+ cache[n+2]*9)%(10**9+7)\n",
    "        #         elif s[n]!=\"*\" and int(s[n])==2:\n",
    "        #             if s[n+1]!=\"*\" and int(s[n+1])<=6:\n",
    "        #                 cache[n]= (cache[n+1]+cache[n+2])%(10**9+7)\n",
    "        #             elif s[n+1]==\"*\":\n",
    "        #                 cache[n]= (cache[n+1]+cache[n+2]*6)%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]=cache[n+1]%(10**9+7)\n",
    "    \n",
    "        #         elif s[n]==\"*\" and s[n+1]!=\"*\" :\n",
    "        #             if  int(s[n+1])<=6:\n",
    "        #                 cache[n]= (9* cache[n+1]  + 2*cache[n+2])%(10**9+7)\n",
    "        #             else:\n",
    "        #                 cache[n]= (9* cache[n+1] + cache[n+2])%(10**9+7)\n",
    "                \n",
    "        #         elif s[n]==\"*\" and s[n+1]==\"*\" :\n",
    "        #             # can't contain numbers that start \"0\" and \"10\",\"20\", totally 11\n",
    "        #             cache[n]= (9* cache[n+1] + 15* cache[n+2])%(10**9+7)\n",
    "        #         else:\n",
    "        #             cache[n] =cache[n+1]%(10**9+7)\n",
    "                    \n",
    "        #         # cache[n] = cache[n]%(10**9+7)\n",
    "        #     else:\n",
    "        #         if s[n]!=\"*\":\n",
    "        #             cache[n] = 1\n",
    "                \n",
    "                    \n",
    "        #         else:\n",
    "        #             cache[n] = 9\n",
    "        # print(cache)   \n",
    "        # return cache[0]%(10**9+7)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        @lru_cache()\n",
    "        def helper(index):\n",
    "            if index == len(s):\n",
    "                return 1\n",
    "            ans = 0\n",
    "            ans1 = 0\n",
    "            if s[index] == '*':\n",
    "                ans1 += 9\n",
    "            elif s[index] == '0':\n",
    "                ans1 += 0\n",
    "            else:\n",
    "                ans1 += 1\n",
    "            ans += ans1*helper(index+1)\n",
    "            ans2 = 0\n",
    "            if index + 1 < len(s):\n",
    "                if s[index+1] != '*':\n",
    "                    if s[index] == '1' or (s[index] == '2' and int(s[index+1]) <= 6):\n",
    "                        ans2 += 1\n",
    "                    elif s[index] == '*':\n",
    "                        if int(s[index+1]) <=6 :\n",
    "                            ans2 += 2\n",
    "                        else:\n",
    "                            ans2 += 1\n",
    "                elif s[index] == '1':\n",
    "                    ans2 += 9\n",
    "                elif s[index] == '2':\n",
    "                    ans2 += 6\n",
    "                elif s[index] == '*':\n",
    "                    ans2 += 15\n",
    "                ans += ans2*helper(index+2)\n",
    "            return ans%(10**9 + 7)\n",
    "        return helper(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        start_chs = \"12\"\n",
    "        start_chs = { ch : True for ch in start_chs }\n",
    "        end_chs = \"34567890\"\n",
    "        end_chs = { ch : True for ch in end_chs }\n",
    "        twenty_end_chs = \"0123456\"\n",
    "        twenty_end_chs = { ch : True for ch in twenty_end_chs }\n",
    "\n",
    "        n = len(s)\n",
    "        m = 10 ** 9 + 7\n",
    "\n",
    "        dp = {}\n",
    "        def innerNumEncodings(ch_idx):\n",
    "            if ch_idx >= n: return 1\n",
    "            \n",
    "            if dp.get(ch_idx) != None:\n",
    "                return dp[ch_idx]\n",
    "\n",
    "            ch = s[ch_idx]\n",
    "\n",
    "            if end_chs.get(ch) != None:\n",
    "                if ch != '0':\n",
    "                    alt = innerNumEncodings(ch_idx + 1)\n",
    "                    alt = alt % m\n",
    "                    dp[ch_idx + 1] = alt\n",
    "                    return alt\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            if start_chs.get(ch) != None:\n",
    "                alt_1 = innerNumEncodings(ch_idx + 1)\n",
    "                alt_1 = alt_1 % m\n",
    "                dp[ch_idx + 1] = alt_1\n",
    "\n",
    "                alt_2 = 0\n",
    "                next_idx = ch_idx + 1\n",
    "                if next_idx < n:\n",
    "                    next_ch = s[next_idx]\n",
    "                    if twenty_end_chs.get(next_ch) != None:\n",
    "                        alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                        alt_2 = alt_2 % m\n",
    "                        dp[ch_idx + 2] = alt_2\n",
    "                    elif next_ch != '*':\n",
    "                        if ch == '1':\n",
    "                            alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                            alt_2 = alt_2 % m\n",
    "                            dp[ch_idx + 2] = alt_2\n",
    "                    else:\n",
    "                        alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                        alt_2 = alt_2 % m\n",
    "                        dp[ch_idx + 2] = alt_2\n",
    "                        alt_2 = 9 * alt_2 if ch == '1' else 6 * alt_2\n",
    "                        alt_2 = alt_2 % m\n",
    "                return alt_1 + alt_2\n",
    "            \n",
    "            if ch == '*':\n",
    "                alt_1 = innerNumEncodings(ch_idx + 1)\n",
    "                alt_1 = alt_1 % m\n",
    "                dp[ch_idx + 1] = alt_1\n",
    "                alt_1 = 9 * alt_1\n",
    "                alt_1 = alt_1 % m\n",
    "\n",
    "                alt_2 = 0\n",
    "                next_idx = ch_idx + 1\n",
    "                if next_idx < n:\n",
    "                    next_ch = s[next_idx]\n",
    "                    if twenty_end_chs.get(next_ch) != None:\n",
    "                        alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                        alt_2 = alt_2 % m\n",
    "                        dp[ch_idx + 2] = alt_2\n",
    "                        alt_2 = 2 * alt_2\n",
    "                        alt_2 = alt_2 % m\n",
    "                    elif next_ch != '*':\n",
    "                        alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                        alt_2 = alt_2 % m\n",
    "                        dp[ch_idx + 2] = alt_2\n",
    "                        alt_2 = alt_2 % m\n",
    "                    else:\n",
    "                        alt_2 = innerNumEncodings(ch_idx + 2)\n",
    "                        alt_2 = alt_2 % m\n",
    "                        dp[ch_idx + 2] = alt_2\n",
    "                        alt_2 = 15 * alt_2\n",
    "                        alt_2 = alt_2 % m\n",
    "                return alt_1 + alt_2\n",
    "        \n",
    "        return innerNumEncodings(0) % m\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "\n",
    "        def num_d(i: int) -> int:\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            if s[i] == \"0\":\n",
    "                return 0\n",
    "            if i in memo:\n",
    "                return memo[i]\n",
    "            else:\n",
    "                if s[i] != \"*\":\n",
    "                    memo[i] = num_d(i + 1)\n",
    "                    if i < len(s) - 1:\n",
    "                        if s[i + 1] != \"*\":\n",
    "                            memo[i] += num_d(i + 2) if s[i: i + 2] <= \"26\" else 0\n",
    "                        else:\n",
    "                            if s[i] == \"1\":\n",
    "                                memo[i] += 9 * num_d(i + 2)\n",
    "                            elif s[i] == \"2\":\n",
    "                                memo[i] += 6 * num_d(i + 2)\n",
    "                else:\n",
    "                    memo[i] = 9 * num_d(i + 1)\n",
    "                    if i < len(s) - 1:\n",
    "                        if s[i + 1] != \"*\":\n",
    "                            memo[i] += 2 * num_d(i + 2) if s[i + 1] <= \"6\" else num_d(i + 2)\n",
    "                        else:\n",
    "                            memo[i] += 15 * num_d(i + 2)\n",
    "                memo[i] %= (10 ** 9 + 7)\n",
    "                return memo[i]\n",
    "        \n",
    "        memo = {}\n",
    "        return num_d(0)\n",
    "        # print(memo)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        def dfs(index):\n",
    "            if index in cache:\n",
    "                return cache[index]\n",
    "            if index == l - 1:\n",
    "                if s[index] == \"*\":\n",
    "                    res = 9\n",
    "                elif s[index] == \"0\":\n",
    "                    res = 0\n",
    "                else:\n",
    "                    res = 1\n",
    "            else:\n",
    "                if s[index] == \"*\":\n",
    "                    res = 9*dfs(index+1)\n",
    "                    if s[index+1] == \"*\":\n",
    "                        if index == l-2:\n",
    "                            res+=15\n",
    "                        else:\n",
    "                            res+=15*dfs(index+2)\n",
    "                    elif s[index+1] < \"7\":\n",
    "                        if index == l-2:\n",
    "                            res+=2\n",
    "                        else:\n",
    "                            res+=2*dfs(index+2)\n",
    "                    else:\n",
    "                        if index == l-2:\n",
    "                            res+=1\n",
    "                        else:\n",
    "                            res+=dfs(index+2)\n",
    "                elif s[index] == \"0\":\n",
    "                    res = 0\n",
    "                elif s[index] == \"1\":\n",
    "                    res = dfs(index+1)\n",
    "                    if s[index+1] == \"*\":\n",
    "                        if index == l-2:\n",
    "                            res += 9\n",
    "                        else:\n",
    "                            res += 9 * dfs(index+2)\n",
    "                    else:\n",
    "                        if index == l-2:\n",
    "                            res+=1\n",
    "                        else:\n",
    "                            res+=dfs(index+2)\n",
    "                elif s[index] == \"2\":\n",
    "                    res = dfs(index+1)\n",
    "                    if s[index+1] == \"*\":\n",
    "                        if index == l-2:\n",
    "                            res += 6\n",
    "                        else:\n",
    "                            res += 6 * dfs(index+2)\n",
    "                    elif s[index+1] < \"7\":\n",
    "                        if index == l-2:\n",
    "                            res+=1\n",
    "                        else:\n",
    "                            res+=dfs(index+2)\n",
    "                else:\n",
    "                    res = dfs(index+1)\n",
    "            cache[index] = res % (10**9+7)\n",
    "            return cache[index]\n",
    "        l = len(s)\n",
    "        cache = {}\n",
    "        return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 记忆化DFS\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        def dfs(i):\n",
    "            if i==0:\n",
    "                return 1\n",
    "            if i in mem:\n",
    "                return mem[i]\n",
    "            flag1 = s[i-1] in d\n",
    "            flag2 = i>1 and s[i-2]+s[i-1] in d\n",
    "            num1 = dfs(i-1)*d[s[i-1]] if flag1 else 0\n",
    "            num2 = dfs(i-2)*d[s[i-2]+s[i-1]] if flag2 else 0\n",
    "            mem[i] = (num1+num2)%MAX\n",
    "            return mem[i]\n",
    "            \n",
    "        n = len(s)\n",
    "        d = {str(a):1 for a in range(1,27)}\n",
    "        d.update({'*%d' % i:sum(1 for j in range(1,10) if str(j)+str(i) in d) for i in range(10)})\n",
    "        d.update({'%d*' % i:sum(1 for j in range(1,10) if str(i)+str(j) in d) for i in range(1,3)})\n",
    "        d.update({'*':9,'**':15})\n",
    "        mem = {}\n",
    "        MAX = 10**9+7\n",
    "        return dfs(n)\n",
    "\n",
    "# 动态规划\n",
    "# class Solution:\n",
    "#     def numDecodings(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         d = {str(a):1 for a in range(1,27)}\n",
    "#         d.update({'*%d' % i:sum(1 for j in range(1,10) if str(j)+str(i) in d) for i in range(10)})\n",
    "#         d.update({'%d*' % i:sum(1 for j in range(1,10) if str(i)+str(j) in d) for i in range(1,3)})\n",
    "#         d.update({'*':9,'**':15})\n",
    "#         MAX = 10**9+7\n",
    "#         dp = [1]+[0]*n\n",
    "#         for i in range(1,n+1):\n",
    "#             if s[i-1] in d:\n",
    "#                 dp[i]=(dp[i]+dp[i-1]*d[s[i-1]])%MAX\n",
    "#             if i>1 and s[i-2]+s[i-1] in d:\n",
    "#                 dp[i]=(dp[i]+dp[i-2]*d[s[i-2]+s[i-1]])%MAX\n",
    "#         return dp[n]\n",
    "\n",
    "# 动态规划+空间优化\n",
    "# class Solution:\n",
    "#     def numDecodings(self, s: str) -> int:\n",
    "#         n = len(s)\n",
    "#         d = {str(a):1 for a in range(1,27)}\n",
    "#         d.update({'*%d' % i:sum(1 for j in range(1,10) if str(j)+str(i) in d) for i in range(10)})\n",
    "#         d.update({'%d*' % i:sum(1 for j in range(1,10) if str(i)+str(j) in d) for i in range(1,3)})\n",
    "#         d.update({'*':9,'**':15})\n",
    "#         MAX = 10**9+7\n",
    "#         dp,pre_pre = 1,0\n",
    "#         for i in range(1,n+1):\n",
    "#             ans = 0\n",
    "#             if s[i-1] in d:\n",
    "#                 ans = (ans+dp*d[s[i-1]])%MAX\n",
    "#             if i>1 and s[i-2]+s[i-1] in d:\n",
    "#                 ans = (ans+pre_pre*d[s[i-2]+s[i-1]])%MAX\n",
    "#             dp,pre_pre = ans,dp\n",
    "#         return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        动态规划\n",
    "        可能性除了dfs也应该可以用动态规划做吧\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        dp = [0]*(n+1)  # dp[i]表示到i为结尾有几种解码可能性\n",
    "\n",
    "        if s[0] == '0':\n",
    "            return 0\n",
    "\n",
    "        dp[0] = 1\n",
    "        if s[0] != '*':\n",
    "            dp[1] = 1\n",
    "        else:\n",
    "            dp[1] = 9\n",
    "\n",
    "        for i in range(2, n+1):\n",
    "            idx = i-1\n",
    "            word = s[idx]\n",
    "            if s[idx-1] in ['0', '3', '4', '5', '6', '7', '8', '9']: # 重新编码\n",
    "                if word == '0':\n",
    "                    return 0\n",
    "                elif word == '*':\n",
    "                    dp[i] = dp[i-1]*9%(10**9+7)\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            elif s[idx-1] == '1':\n",
    "                if word == '0':\n",
    "                    dp[i] = dp[i-2]\n",
    "                elif word == '*':\n",
    "                    dp[i] = (dp[i-1]*9 + dp[i-2]*9)%(10**9+7)\n",
    "                else:\n",
    "                    dp[i] = dp[i-1] + dp[i-2]\n",
    "            elif s[idx-1] == '2':\n",
    "                if word == '0':\n",
    "                    dp[i] = dp[i-2]\n",
    "                elif word == '*':\n",
    "                    dp[i] = (dp[i-1]*9 + dp[i-2]*6)%(10**9+7)\n",
    "                elif int(word)<=6:\n",
    "                    dp[i] = dp[i-2] + dp[i-1]\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            elif s[idx-1] == '*':\n",
    "                if word == '0':\n",
    "                    dp[i] = dp[i-2]*2\n",
    "                elif word in ['1', '2', '3', '4', '5', '6']:\n",
    "                    dp[i] = dp[i-1] + dp[i-2]*2\n",
    "                elif word in ['7', '8', '9']:\n",
    "                    dp[i] = dp[i-1] + dp[i-2]\n",
    "                else:\n",
    "                    dp[i] = (dp[i-1]*9 + dp[i-2]*15)%(10**9+7)\n",
    "        return dp[n]%(10**9+7)\n",
    "                \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import lru_cache,cache\n",
    "class Solution:\n",
    "    def numDecodings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = s + '#'\n",
    "        mod = int(1e9+7)\n",
    "        # 11 12 13 14 15 16 17 18 19 \n",
    "        # 21 22 23 24 25 26\n",
    "        @cache\n",
    "        def f(x:int)->int:\n",
    "            if x == n:\n",
    "                return 1\n",
    "            if s[x] == '0':\n",
    "                return 0\n",
    "            res = 0\n",
    "            if s[x] == '*' and s[x + 1] == '*':\n",
    "                res += 9 * f(x + 1)\n",
    "                res += 15 * f(x + 2)\n",
    "            elif s[x] == '*' and s[x+1] == '#':\n",
    "                res += 9 * f(x + 1)\n",
    "            elif s[x] == '*' and s[x+1] != '*':\n",
    "                res += 9 * f(x + 1)\n",
    "                if int(s[x+1]) <= 6:\n",
    "                    res += 2 * f(x + 2)\n",
    "                else:\n",
    "                    res += f(x+2)\n",
    "            elif s[x] != '*' and s[x+1] == '#':\n",
    "                res += f(x + 1)\n",
    "            elif s[x] != '*' and s[x+1] == '*':\n",
    "                res += f(x + 1)\n",
    "                if s[x] == '1':\n",
    "                    res += 9 * f(x + 2)\n",
    "                elif s[x] == '2':\n",
    "                    res += 6 * f(x + 2)\n",
    "            elif s[x] != '*' and s[x+1] != '*':\n",
    "                res += f(x + 1)\n",
    "                if int(s[x] + s[x+1]) <= 26:\n",
    "                    res += f(x +2)\n",
    "            res %= mod\n",
    "            return res\n",
    "        return f(0)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
